Giáo trình Lý thuyết đồ họa
MꢀC LꢀC
Chương 1: CÁC YꢁU Tꢂ CƠ Sꢃ CꢄA ðꢅ HꢆA
1.1. Tꢇng quan vꢈ ñꢉ hꢊa máy tính ............................................................................... 1
1.1.1. Giꢀi thiꢁu vꢂ ñꢃ hꢄa máy tính ................................................................................ 1
1.1.2. Các kꢅ thuꢆt ñꢃ hꢄa ................................................................................................ 1
1.1.2.1. Kꢅ thuꢆt ñꢃ hꢄa ñiꢇm........................................................................................ 1
1.1.2.2. Kꢅ thuꢆt ñꢃ hꢄa vector...................................................................................... 2
1.1.3. ꢈng dꢉng cꢊa ñꢃ hꢄa máy tính............................................................................... 2
1.1.4. Các lĩnh vꢋc cꢊa ñꢃ hꢄa máy tính .......................................................................... 3
1.1.5. Tꢌng quan vꢂ mꢍt hꢁ ñꢃ hꢄa .................................................................................. 4
1.2. Màn hình ñꢉ hꢊa...................................................................................................... 6
1.3. Các khái niꢋm........................................................................................................... 6
1.3.1. ðiꢇm..................................................................................................................... 6
1.3.2. Các biꢇu diꢎn tꢄa ñꢍ ............................................................................................ 8
1.3.3. ðoꢏn thꢐng........................................................................................................... 8
1.4. Các thuꢌt toán vꢍ ñoꢎn thꢏng................................................................................. 8
1.4.1. Bài toán................................................................................................................ 8
1.4.2. Thuꢆt toán DDA................................................................................................... 9
1.4.3. Thuꢆt toán Bresenham ....................................................................................... 10
1.4.4. Thuꢆt toán MidPoint.......................................................................................... 12
1.5. Thuꢌt toán vꢍ ñưꢐng tròn..................................................................................... 14
1.5.1. Thuꢆt toán Bresenham ....................................................................................... 14
1.5.2. Thuꢆt toán MidPoint.......................................................................................... 16
1.6. Thuꢌt toán vꢍ Ellipse............................................................................................. 17
1.6.1. Thuꢆt toán Bresenham ....................................................................................... 17
1.6.2. Thuꢆt toán MidPoint.......................................................................................... 20
1.7. Phương pháp vꢍ ñꢉ thꢑ hàm sꢒ ............................................................................. 21
Bài tꢌp............................................................................................................................ 23
Chương 2: TÔ MÀU
2.1. Giꢓi thiꢋu các hꢋ màu............................................................................................ 25
2.2. Các thuꢌt toán tô màu .......................................................................................... 28
2.2.1. Bài toán.............................................................................................................. 28
2.2.2. Thuꢆt toán xác ñꢑnh P S ................................................................................. 28
2.2.3. Thuꢆt toán tô màu theo dòng quét ..................................................................... 30
2.2.4. Thuꢆt toán tô màu theo vꢒt dꢓu loang................................................................ 30
Bài tꢌp............................................................................................................................ 31
Chương 3: XÉN HÌNH
3.1. ðꢔt vꢕn ñꢈ............................................................................................................... 32
3.2. Xén ñoꢎn thꢏng vào vùng hình chꢖ nhꢌt............................................................. 32
3.2.1. Cꢏnh cꢊa hình chꢔ nhꢆt song song vꢀi các trꢉc tꢄa ñꢍ ..................................... 32
3.2.1.1. Thuꢆt toán Cohen – Sutherland ...................................................................... 33
3.2.1.2. Thuꢆt toán chia nhꢑ phân................................................................................. 34
3.2.1.3. Thuꢆt toán Liang – Barsky ............................................................................. 35
3.2.2. Khi cꢏnh cꢊa hình chꢔ nhꢆt tꢏo vꢀi trꢉc hoành mꢍt góc α................................ 36
3.3. Xén ñoꢎn thꢏng vào hình tròn.............................................................................. 37
3.4. Xén ñưꢐng tròn vào hình chꢖ nhꢌt...................................................................... 38
3.5. Xén ña giác vào hình chꢖ nhꢌt ............................................................................. 39
Bài tꢌp............................................................................................................................ 40
Chương 4: CÁC PHÉP BIꢁN ðꢗI
4.1. Các phép biꢘn ñꢇi trong mꢔt phꢏng..................................................................... 41
4.1.1. Cơ sꢕ toán hꢄc ................................................................................................... 41
4.1.2. Ví dꢉ minh hꢄa .................................................................................................. 43
4.2. Các phép biꢘn ñꢇi trong không gian.................................................................... 45
4.2.1. Các hꢁ trꢉc tꢄa ñꢍ .............................................................................................. 45
4.2.2. Các công thꢖc biꢒn ñꢌi ...................................................................................... 46
4.2.3. Ma trꢆn nghꢑch ñꢗo ............................................................................................ 48
4.3. Các phép chiꢘu cꢙa vꢌt thꢚ trong không gian lên mꢔt phꢏng ........................... 48
4.3.1. Phép chiꢒu phꢘi cꢗnh......................................................................................... 48
4.3.2. Phép chiꢒu song song......................................................................................... 50
4.4. Công thꢛc cꢙa các phép chiꢘu lên màn hình....................................................... 50
4.5. Phꢜ lꢜc .................................................................................................................... 56
4.6. Ví dꢜ minh hꢊa....................................................................................................... 59
Bài tꢌp............................................................................................................................ 61
Chương 5: BIꢝU DIꢞN CÁC ðꢂI TƯꢟNG BA CHIꢠU
5.1. Mô hình WireFrame.............................................................................................. 63
5.2. Vꢍ mô hình WireFrame vꢓi các phép chiꢘu........................................................ 64
5.3. Vꢍ các mꢔt toán hꢊc............................................................................................... 65
Bài tꢌp............................................................................................................................ 68
Chương 6: THIꢁT Kꢁ ðƯꢡNG VÀ MꢢT CONG BEZIER VÀ B-SPLINE
6.1. ðưꢐng cong Bezier và mꢔt Bezier........................................................................ 69
6.1.1. Thuꢆt toán Casteljau .......................................................................................... 70
6.1.2. Dꢏng Bernstein cꢊa ñưꢙng cong Bezier ............................................................ 70
6.1.3. Dꢏng biꢇu diꢎn ma trꢆn cꢊa ñưꢙng Bezier ........................................................ 71
6.1.4. Tꢏo và vꢚ ñưꢙng cong Bezier............................................................................ 72
6.1.5. Các tính chꢛt cꢊa ñưꢙng Bezier......................................................................... 74
6.1.6. ðánh giá các ñưꢙng cong Bezier....................................................................... 76
6.2. ðưꢐng cong Spline và B-Spline............................................................................ 77
6.2.1. ðꢑnh nghĩa.......................................................................................................... 77
6.2.2. Các tính chꢛt hꢔu ích trong viꢁc thiꢒt kꢒ các ñưꢙng cong B-Spline ................. 78
6.2.3. Thiꢒt kꢒ các mꢜt Bezier và B-Spline ................................................................. 79
6.2.4. Các băng Bezier................................................................................................. 80
6.2.5. Dán các băng Bezier vꢀi nhau ........................................................................... 81
6.2.6. Các băng B-Spline ............................................................................................. 81
Chương 7: KHꢣ ðƯꢡNG VÀ MꢢT KHUꢤT
7.1. Các khái niꢋm......................................................................................................... 83
7.2. Các phương pháp khꢥ mꢔt khuꢕt........................................................................ 85
7.2.1. Giꢗi thuꢆt sꢝp xꢒp theo chiꢂu sâu ...................................................................... 85
7.2.2. Giꢗi thuꢆt BackFace........................................................................................... 88
7.2.3. Giꢗi thuꢆt vùng ñꢁm ñꢍ sâu ............................................................................... 90
Bài tꢌp.......................................................................................................................... 103
Chương 8: TꢦO BÓNG VꢧT THꢝ 3D
8.1. Khái niꢋm ............................................................................................................. 104
8.2. Nguꢉn sáng xung quanh...................................................................................... 104
8.3. Nguꢉn sáng ñꢑnh hưꢓng ...................................................................................... 105
8.4. Nguꢉn sáng ñiꢚm.................................................................................................. 109
8.5. Mô hình bóng Gouraud....................................................................................... 110
Bài tꢌp.......................................................................................................................... 121
Phꢜ lꢜc: MꢨT Sꢂ CHƯƠNG TRÌNH MINH HꢆA
I. Các thuꢌt toán tô màu ............................................................................................ 122
II. Các thuꢌt toán xén hình........................................................................................ 129
III. Vꢍ các ñꢒi tưꢩng 3D............................................................................................. 136
Tài liꢋu tham khꢪo...................................................................................................... 143
LꢀI Mꢁ ðꢂU
ðꢀ hꢁa là mꢂt trong nhꢃng lĩnh vꢄc phát triꢅn rꢆt nhanh cꢇa ngành Công nghꢈ
thông tin. Nó ñưꢉc ꢊng dꢋng rꢂng rãi trong nhiꢌu lĩnh vꢄc khoa hꢁc và công nghꢈ.
Chꢍng hꢎn như y hꢁc, kiꢏn trúc, giꢐi trí... ðꢀ hꢁa máy tính ñã giúp chúng ta thay ñꢑi
cách cꢐm nhꢒn và sꢓ dꢋng máy tính, nó ñã trꢔ thành nhꢃng công cꢋ trꢄc quan quan
trꢁng không thꢅ thiꢏu trong ñꢕi sꢖng hꢗng ngày. Vì vꢒy môn “ðꢀ hꢁa” ñã trꢔ thành
mꢂt trong nhꢃng môn hꢁc chính trong các chuyên ngành Công nghꢈ thông tin ꢔ các
trưꢕng ñꢎi hꢁc.
Cuꢖn sách “Giáo trình lý thuyꢏt ñꢀ hꢁa” ñưꢉc biên soꢎn theo sát nꢂi dung
chương trình ñào tꢎo cꢓ nhân Công nghꢈ thông tin. Nꢂi dung cꢇa giáo trình này
cung cꢆp mꢂt sꢖ kiꢏn thꢊc cơ bꢐn vꢌ lý thuyꢏt và thuꢒt toán xây dꢄng các công cꢋ
ñꢀ hꢁa 2D và 3D. Tꢘ ñó giúp sinh viên có thꢅ ñꢂc lꢒp xây dꢄng nhꢃng thư viꢈn ñꢀ
hꢁa cho riêng mình và phát triꢅn các phꢙn mꢌm ꢊng dꢋng ñꢀ hꢁa cao hơn.
Giáo trình ñưꢉc chia làm 8 chương và phꢙn phꢋ lꢋc, sau mꢚi chương ñꢌu có
phꢙn bài tꢒp ñꢅ kiꢅm tra kiꢏn thꢊc và rèn luyꢈn khꢐ năng lꢒp trình cho bꢎn ñꢁc. ðꢅ
thuꢒn tiꢈn cho viꢈc trình bày thuꢒt toán mꢂt cách dꢅ hiꢅu, các giꢐi thuꢒt trong giáo
trình ñưꢉc viꢏt trên ngôn ngꢃ “tꢄa Pascal” và các mã nguꢀn ñưꢉc cài ñꢛt trên Turbo
Pascal 7.0. Nhꢗm giúp bꢎn ñꢁc bꢜt lúng túng trong quá trình cài ñꢛt các giꢐi thuꢒt,
phꢙn phꢋ lꢋc liꢈt kê mꢂt sꢖ mã nguꢀn cài ñꢛt các thuꢒt toán trong các chương. Tuy
nhiên, bꢎn ñꢁc nên tꢄ cài ñꢛt các thuꢒt toán ꢔ phꢙn lý thuyꢏt, nꢏu cꢐm thꢆy khó
khăn lꢝm mꢜi nên tham khꢐo phꢙn phꢋ lꢋc này.
Chương 1, 2 và 3 trình bày vꢌ các yꢏu tꢖ cơ sꢔ cꢇa ñꢀ hꢁa như: màn hình ñꢀ
hꢁa, ñiꢅm, ñoꢎn thꢞng, ñưꢕng tròn, các hꢈ màu và các thuꢒt toán tô màu, xén hình ...
Chương 4 trang bꢟ các kiꢏn thꢊc toán hꢁc vꢌ các phép biꢏn ñꢑi trong không gian 2D
và 3D. Chương 5, 6 và 7 giꢜi thiꢈu các mô hình ñꢀ hꢁa 3D, các giꢐi thuꢒt khꢓ mꢛt
khuꢆt và tꢎo bóng cho vꢒt thꢅ... Chương 8 trình bày vꢌ phương pháp thiꢏt kꢏ các
ñưꢕng cong Bezier và B-Spline.
Mꢛc dù ñã rꢆt cꢖ gꢝng trong quá trình biên soꢎn nhưng chꢝc chꢝn giáo trình
này vꢠn không thꢅ tránh khꢡi nhꢃng thiꢏu sót. Chúng tôi rꢆt mong nhꢒn ñưꢉc nhꢃng
ý kiꢏn ñóng góp cꢇa bꢎn ñꢁc cũng như các bꢎn ñꢀng nghiꢈp trong lĩnh vꢄc ðꢀ hꢁa
ñꢅ giáo trình ngày càng ñưꢉc hoàn thiꢈn hơn trong lꢙn tái bꢐn sau. ðꢟa chꢢ liên lꢎc:
Khoa Công nghꢀ Thông tin, trưꢁng ðꢂi hꢃc Khoa hꢃc Huꢄ.
Huꢃ, tháng 08 năn 2003
Các tác giꢄ
Updatesofts.com
Ebooks Team
CHƯƠNG I
CÁC YꢀU Tꢁ CƠ Sꢂ CꢃA ðꢄ HꢅA
1.1. TꢆNG QUAN Vꢇ ðꢄ HꢅA MÁY TÍNH
ðꢀ hꢁa máy tính là mꢂt lãnh vꢃc phát triꢄn nhanh nhꢅt trong Tin hꢁc. Nó ñưꢆc áp
dꢇng rꢂng rãi trong nhiꢈu lãnh vꢃc khác nhau thuꢂc vꢈ khoa hꢁc, kꢉ nghꢊ, y khoa,
kiꢋn trúc và giꢌi trí.
Thuꢍt ngꢎ ñꢈ hꢉa máy tính (Computer Graphics) ñưꢆc ñꢈ xuꢅt bꢏi nhà khoa hꢁc
ngưꢐi Mꢉ tên là William Fetter vào năm 1960 khi ông ñang nghiên cꢑu xây dꢃng mô
hình buꢀng lái máy bay cho hãng Boeing.
Các chương trình ñꢀ hꢁa ꢑng dꢇng cho phép chúng ta làm viꢊc vꢒi máy tính mꢂt
cách thoꢌi mái, tꢃ nhiên.
1.1.1 Giꢊi thiꢋu vꢌ ñꢈ hꢉa máy tính
ðꢀ hꢁa máy tính là mꢂt ngành khoa hꢉc Tin hꢉc chuyên nghiên cꢑu vꢈ các
phương pháp và kꢍ thuꢎt ñꢄ có thꢄ mô tꢌ và thao tác trên các ñꢓi tưꢆng cꢔa thꢋ giꢒi
thꢃc bꢕng máy tính.
Vꢈ bꢌn chꢅt: ñó là mꢂt quá trình xây dꢏng và phát triꢐn các công cꢇ trên cꢌ hai
lĩnh vꢃc phꢖn cꢑng và phꢖn mꢈm hꢗ trꢆ cho các lꢍp trình viên thiꢋt kꢋ các chương
trình có khꢌ năng ñꢀ hꢁa cao.
Vꢒi viꢊc mô tꢑ dꢒ liꢋu thông qua các hình ꢑnh và màu sꢓc ña dꢘng cꢔa nó, các
chương trình ñꢀ hꢁa thưꢐng thu hút ngưꢐi sꢙ dꢇng bꢏi tính thân thiꢊn, dꢄ dùng,... kích
thích khꢌ năng sáng tꢘo và nâng cao năng suꢅt làm viꢊc.
1.1.2. CÁC Kꢔ THUꢕT ðꢄ HꢅA
Dꢃa vào các phương pháp xꢙ lý dꢎ liꢊu trong hꢊ thꢓng, ta phân ra làm hai kꢉ thuꢍt
ñꢀ hꢁa:
1.1.2.1. Kꢍ thuꢎt ñꢈ hꢉa ñiꢐm
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
Nguyên lý cꢔa kꢉ thuꢍt này như sau: các hình ꢌnh ñưꢆc hiꢄn thꢚ thông qua tꢛng
pixel (tꢛng mꢜu rꢐi rꢘc). Vꢒi kꢉ thuꢍt này, chúng ta có thꢄ tꢘo ra, xóa hoꢝc thay ñꢗi
thuꢂc tính cꢔa tꢛng pixel cꢔa các ñꢓi tưꢆng. Các hình ꢌnh ñưꢆc hiꢄn thꢚ như mꢂt lưꢒi
ñiꢄm rꢐi rꢘc (grid), tꢛng ñiꢄm ñꢈu có vꢚ trí xác ñꢚnh ñưꢆc hiꢄn thꢚ vꢒi mꢂt giá trꢚ
nguyên biꢄu thꢚ màu sꢞc hoꢝc dꢂ sáng cꢔa ñiꢄm ñó. Tꢍp hꢆp tꢅt cꢌ các pixel cꢔa grid
tꢘo nên hình ꢌnh cꢔa ñꢓi tưꢆng mà ta muꢓn biꢄu diꢟn.
1.1.2.2. Kꢍ thuꢎt ñꢈ hꢉa vector
Nguyên lý cꢔa kꢉ thuꢍt này là xây dꢃng mô hình hình hꢁc (geometrical model) cho
hình ꢌnh ñꢓi tưꢆng, xác ñꢚnh các thuꢂc tính cꢔa mô hình hình hꢁc, sau ñó dꢃa trên mô
hình này ñꢄ thꢃc hiꢊn quá trình tô trát (rendering) ñꢄ hiꢄn thꢚ tꢛng ñiꢄm cꢔa mô hình,
hình ꢌnh cꢔa ñꢓi tưꢆng.
ꢠ kꢉ thuꢍt này, chúng ta chꢡ lưu trꢎ mô hình toán hꢁc cꢔa các thành phꢖn trong mô
hình hình hꢁc cùng vꢒi các thuꢂc tính tương ꢑng mà không cꢖn lưu lꢘi toàn bꢂ tꢅt cꢌ
các pixel cꢔa hình ꢌnh ñꢓi tưꢆng.
1.1.3. ꢚng dꢛng cꢙa ñꢈ hꢉa máy tính hiꢋn nay
Ngày nay, ñꢀ hꢁa máy tính ñưꢆc sꢙ dꢇng rꢂng rãi trong nhiꢈu lĩnh vꢃc khác
nhau như: Công nghiꢊp, thương mꢘi, quꢌn lý, giáo dꢇc, giꢌi trí,... Sau ñây là mꢂt sꢓ
ꢑng dꢇng tiêu biꢄu:
1.1.3.1. Tꢀo giao diꢁn (User Interfaces): như các chương trình ꢑng dꢇng WINDOWS,
WINWORD, EXCEL ... ñang ñưꢆc ña sꢓ ngưꢐi sꢙ dꢇng ưa chuꢂng nhꢐ tính thân
thiꢊn, dꢄ sꢙ dꢇng.
1.1.3.2. Tꢀo ra các biꢂu ñꢃ dùng trong thương mꢀi, khoa hꢄc và kꢅ thuꢆt: Các biꢄu
ñꢀ ñưꢆc tꢘo ra rꢅt ña dꢘng, phong phú bao gꢀm cꢌ hai chiꢈu lꢜn ba chiꢈu góp phꢖn
thúc ñꢢy xu hưꢒng phát triꢄn các mô hình dꢎ liꢊu hꢗ trꢆ ñꢞc lꢃc cho viꢊc phân tích
thông tin và trꢆ giúp ra quyꢋt ñꢚnh.
1.1.3.3. Tꢇ ñꢈng hóa văn phòng và chꢉ bꢊn ñiꢁn tꢋ: dùng nhꢎng ꢑng dꢇng cꢔa ñꢀ
hꢁa ñꢄ in ꢅn các tài liꢊu vꢒi nhiꢈu loꢘi dꢎ liꢊu khác nhau như: văn bꢌn, biꢄu ñꢀ, ñꢀ thꢚ
và nhiꢈu loꢘi hình ꢌnh khác ...
1.1.3.4. Thiꢉt kꢉ vꢌi sꢇ trꢍ giúp cꢎa máy tính (Computer aided design): Mꢂt trong
nhꢎng lꢆi ích lꢒn nhꢅt cꢔa máy tính là trꢆ giúp con ngưꢐi trong viꢊc thiꢋt kꢋ. Các ꢑng
2
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
dꢇng ñꢀ hꢁa cho phép chúng ta thiꢋt kꢋ các thiꢋt bꢚ cơ khí, ñiꢊn, ñiꢊn tꢙ, ô tô, máy bay,
... như phꢖn mꢈm AUTOCAD ...
1.1.3.5. Lĩnh vꢇc giꢊi trí, nghꢁ thuꢆt: cho phép các hꢁa sĩ tꢘo ra các hình ꢌnh ngay
trên màn hình cꢔa máy tính. Ngưꢐi hꢁa sĩ có thꢄ tꢃ pha màu, trꢂn màu, thꢃc hiꢊn mꢂt
sꢓ thao tác: cꢞt, dán, tꢢy, xóa, phóng to, thu nhꢣ ... như các phꢖn mꢈm PAINTBRUSH,
CORELDRAW,...
1.1.3.6. Lĩnh vꢇc bꢊn ñꢃ: xây dꢃng và in ꢅn các bꢌn ñꢀ ñꢚa lý. Mꢂt trong nhꢎng ꢑng
dꢇng hiꢊn nay cꢔa ñꢀ hꢁa là hꢊ thꢓng thông tin ñꢚa lý (GIS - Geographical Information
System).
1.1.4. Các lĩnh vꢏc cꢙa ñꢈ hꢉa máy tính
1.1.4.1. Các hꢋ CAD/CAM (CAD – Computer Aided Design, CAM – Computer
Aided Manufacture)
Các hꢊ này xây dꢃng tꢍp hꢆp các công cꢇ ñꢀ hꢁa trꢆ giúp cho viꢊc thiꢋt kꢋ các chi
tiꢋt và các hꢊ thꢓng khác nhau: các thiꢋt bꢚ cơ khí, ñiꢊn tꢙ... Chꢤng hꢘn như phꢖn mꢈm
Auto Cad cꢔa hꢌng AutoDesk...
1.1.4.2. Xꢜ lý ꢑnh (Image Processing)
ðây là lĩnh vꢃc xꢙ lý các dꢎ liꢊu ꢌnh trong cuꢂc sꢓng. Sau quá trình xꢙ lý ꢌnh, dꢎ
liꢊu ñꢖu ra là ꢌnh cꢔa ñꢓi tưꢆng. Trong quá trình xꢙ lý ꢌnh, chúng ta sꢥ sꢙ dꢇng rꢅt
nhiꢈu các kꢉ thuꢍt phꢑc tꢘp: khôi phꢇc ꢌnh, xác ñꢚnh biên...
Ví dꢇ: phꢖn mꢈm PhotoShop, Corel Draw, ...
1.1.4.3. Khoa hꢉc nhꢎn dꢝng (Pattern Recognition)
Nhꢍn dꢘng là mꢂt lĩnh vꢃc trong kꢉ thuꢍt xꢙ lý ꢌnh. Tꢛ nhꢎng mꢜu ꢌnh có sꢦn, ta
phân loꢘi theo cꢅu trúc hoꢝc theo các phương pháp xác ñꢚnh nào ñó và bꢕng các thuꢍt
toán chꢁn lꢁc ñꢄ có thꢄ phân tích hay tꢗng hꢆp ꢌnh ñã cho thành mꢂt tꢍp hꢆp các ꢌnh
gꢓc, các ꢌnh gꢓc này ñưꢆc lưu trong mꢂt thư viꢊn và căn cꢑ vào thư viꢊn này ñꢄ nhꢍn
dꢘng các ꢌnh khác.
Ví dꢇ: Phꢖn mꢈm nhꢍn dꢘng chꢎ viꢋt (VnDOCR) cꢔa viꢊn Công nghꢊ Thông tin
Hà Nꢂi, nhꢍn dꢘng vân tay, nhꢍn dꢘng mꢝt ngưꢐi trong khoa hꢁc hình sꢃ...
1.1.4.4. ðꢈ hꢉa minh hꢉa (Presentation Graphics)
3
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
ðây là lĩnh vꢃc ñꢀ hꢁa bao gꢀm các công cꢇ trꢆ giúp cho viꢊc hiꢄn thꢚ các sꢓ liꢊu
thꢓng kê mꢂt cách trꢃc quan thông qua các mꢜu ñꢀ thꢚ hoꢝc biꢄu ñꢀ có sꢦn. Chꢤng hꢘn
như các biꢄu ñꢀ (Chart) trong các phꢖn mꢈm Word, Excel...
1.1.4.5. Hoꢝt hình và nghꢋ thuꢎt
Lĩnh vꢃc ñꢀ hꢁa này bao gꢀm các công cꢇ giúp cho các hꢁa sĩ, các nhà thiꢋt kꢋ
phim ꢌnh chuyên nghiꢊp thꢃc hiꢊn các công viꢊc cꢔa mình thông qua các kꢉ xꢌo vꢥ
tranh, hoꢘt hình hoꢝc các kꢉ xꢌo ñiꢊn ꢌnh khác...
Ví dꢇ: Phꢖn mꢈm xꢙ lý các kꢉ xꢌo hoꢘt hình như: 3D Animation, 3D Studio
Max..., phꢖn mꢈm xꢙ lý các kꢉ xꢌo ñiꢊn ꢌnh: Adobe Primiere, Cool 3D,...
1.1.5. Tꢞng quan vꢌ mꢟt hꢋ ñꢈ hꢉa (Graphics System)
1.1.5.1. Hꢋ thꢗng ñꢈ hꢉa
Phꢏn mꢐm ñꢃ hꢄa: Là tꢍp hꢆp các câu lꢊnh ñꢀ hꢁa cꢔa hꢊ thꢓng. Các câu lꢊnh lꢍp
trình dùng cho các thao tác ñꢀ hꢁa không ñưꢆc các ngôn ngꢎ lꢍp trình thông dꢇng như
PASCAL, C, ... hꢗ trꢆ. Thông thưꢐng, nó chꢡ cung cꢅp như là mꢂt tꢍp công cꢇ thêm
vào trong ngôn ngꢎ. Tꢍp các công cꢇ này dùng ñꢄ tꢘo ra các thành phꢖn cơ sꢏ cꢔa mꢂt
hình ꢌnh ñꢀ hꢁa như: ðiꢄm, ñoꢘn thꢤng, ñưꢐng tròn, màu sꢞc,... Qua ñó, các nhà lꢍp
trình phꢌi tꢘo ra các chương trình ñꢀ hꢁa có khꢌ năng ꢑng dꢇng cao hơn.
Phꢏn cꢑng ñꢃ hꢄa: Là các thiꢋt bꢚ ñiꢊn tꢙ: CPU, Card, màn hình, chuꢂt, phím...
giúp cho viꢊc thꢃc hiꢊn và phát triꢄn các phꢖn mꢈm ñꢀ hꢁa.
1.1.5.2. Các thành phꢠn cꢙa mꢟt hꢋ thꢗng ñꢈ hꢉa
Tꢍp hꢆp các công cꢇ này ñưꢆc phân loꢘi dꢃa trên nhꢎng công viꢊc trong tꢛng hoàn
cꢌnh cꢇ thꢄ: xuꢅt, nhꢍp, biꢋn ñꢗi ꢌnh, ... bao gꢀm:
• Tꢎp công cꢛ tꢝo ra ꢑnh gꢗc (output primitives): cung cꢅp các công cꢇ cơ bꢌn
nhꢅt cho viꢊc xây dꢃng các hình ꢌnh. Các ꢌnh gꢓc bao gꢀm các chuꢧi ký tꢃ, các thꢃc
thꢄ hình hꢁc như ñiꢄm, ñưꢐng thꢤng, ña giác, ñưꢐng tròn,...
• Tꢎp các công cꢛ thay ñꢞi thuꢟc tính (attributes): dùng ñꢄ thay ñꢗi thuꢂc tính cꢔa
các ꢌnh gꢓc. Các thuꢂc tính cꢔa ꢌnh gꢓc bao gꢀm màu sꢞc (color), kiꢄu ñưꢐng thꢤng
(line style), kiꢄu văn bꢌn (text style), mꢜu tô vùng (area filling pattern),...
4
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
• Tꢎp các công cꢛ thay ñꢞi hꢋ quan sát (viewing transformation): Mꢂt khi mà các
ꢌnh gꢓc và các thuꢂc tính cꢔa nó ñưꢆc xác ñꢚnh trong hꢊ tꢁa ñꢂ thꢃc, ta cꢖn phꢌi chiꢋu
phꢖn quan sát cꢔa ꢌnh sang mꢂt thiꢋt bꢚ xuꢅt cꢇ thꢄ. Các công cꢇ này cho phép ñꢚnh
nghĩa các vùng quan sát trên hꢊ tꢁa ñꢂ thꢃc ñꢄ hiꢄn thꢚ hình ꢌnh ñó.
• Tꢎp các công cꢛ phꢛc vꢛ cho các thao tác nhꢎp dꢒ liꢋu (input operations): Các
ꢑng dꢇng ñꢀ hꢁa có thꢄ sꢙ dꢇng nhiꢈu loꢘi thiꢋt bꢚ nhꢍp khác nhau như bút vꢥ, bꢌng,
chuꢂt, ... Chính vì vꢍy, cꢖn xây dꢃng thêm các công cꢇ này ñꢄ ñiꢈu khiꢄn và xꢙ lý các
dꢎ liꢊu nhꢍp sao cho có hiꢊu quꢌ.
Mꢂt yêu cꢖu vꢈ phꢖn cꢑng không thꢄ thiꢋu ñꢝt ra cho các phꢖn mꢈm ñꢀ hꢁa là:
tính dꢟ mang chuyꢄn (portability), có nghĩa là chương trình có thꢄ chuyꢄn ñꢗi mꢂt
cách dꢟ dàng giꢎa các kiꢄu phꢖn cꢑng khác nhau. Nꢋu không có sꢃ chuꢢn hóa, các
chương trình thiꢋt kꢋ thưꢐng không thꢄ chuyꢄn ñꢗi ñꢋn các hꢊ thꢓng phꢖn cꢑng khác
mà không viꢋt lꢘi gꢖn như toàn bꢂ chương trình.
Sau nhꢎng nꢗ lꢃc cꢔa các tꢗ chꢑc chuꢢn hóa quꢓc tꢋ, mꢂt chuꢢn cho viꢊc phát triꢄn
các phꢖn mꢈm ñꢀ hꢁa ñã ra ñꢐi: ñó là GKS (Graphics Kernel System - Hꢊ ñꢀ hꢁa cơ
sꢏ). Hꢊ thꢓng này ban ñꢖu ñưꢆc thiꢋt kꢋ như là mꢂt tꢍp các công cꢇ ñꢀ hꢁa hai chiꢈu,
sau ñó ñưꢆc phát triꢄn ñꢄ mꢏ rꢂng trong ñꢀ hꢁa ba chiꢈu.
Ngoài ra, còn có mꢂt sꢓ chuꢢn ñꢀ hꢁa phꢗ biꢋn như:
•
CGI (Computer Graphics Interface System): hꢊ chuꢢn cho các phương pháp
giao tiꢋp vꢒi các thiꢋt bꢚ ngoꢘi vi.
•
•
OPENGL: thư viꢊn ñꢀ hꢁa cꢔa hꢌng Silicon Graphics.
DIRECTX: thư viꢊn ñꢀ hꢁa cꢔa hꢌng Microsoft.
1.2. MÀN HÌNH ðꢄ HꢅA
Mꢧi máy tính ñꢈu có mꢂt CARD dùng ñꢄ quꢌn lý màn hình, gꢁi là Video Adapter
hay Graphics Adapter. Có nhiꢈu loꢘi adapter như: CGA, MCGA, EGA, VGA,
Hercules... Các adapter có thꢄ làm viꢊc ꢏ hai chꢋ ñꢂ: văn bꢌn (Text Mode) và ñꢀ hꢁa
(Graphics Mode).
Có nhiꢈu cách ñꢄ khꢏi tꢘo các mode ñꢀ hꢁa. Ta có thꢄ sꢙ dꢇng hàm $00 ngꢞt $10
cꢔa BIOS vꢒi các Mode sau:
5
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
Mode $12: chꢋ ñꢂ phân giꢌi 640x480x16
Mode $13: chꢋ ñꢂ phân giꢌi 320x200x256
•
•
Ta có thꢄ viꢋt mꢂt thꢔ tꢇc ñꢄ khꢏi tꢘo chꢋ ñꢂ ñꢀ hꢁa như sau:
Procedure InitGraph(Mode:Word);
var Reg:Registers;
Begin
reg.ah := 0;
reg.al := mode;
intr($10,reg);
End;
Các bꢀn có thꢂ tham khꢊo thêm ꢒ các tài liꢁu vꢐ lꢆp trình hꢁ thꢓng.
1.3. CÁC KHÁI NIꢡM
1.3.1. ðiꢐm (Pixel)
Trong các hꢊ thꢓng ñꢀ hꢁa, mꢂt ñiꢄm ñưꢆc biꢄu thꢚ bꢏi các tꢁa ñꢂ bꢕng sꢓ.
Ví du: Trong mꢝt phꢤng, mꢂt ñiꢄm là mꢂt cꢝp (x,y)
Trong không gian ba chiꢈu, mꢂt ñiꢄm là bꢂ ba (x,y,z)
Trên màn hình cꢔa máy tính, mꢂt ñiꢄm là mꢂt vꢚ trí trong vùng nhꢒ màn hình dùng
ñꢄ lưu trꢎ các thông tin vꢈ ñꢂ sáng cꢔa ñiꢄm tương ꢑng trên màn hình.
Sꢓ ñiꢄm vꢥ trên màn hình ñưꢆc gꢁi là ñꢈ phân giꢊi cꢔa màn hình (320x200,
480x640, 1024x1024,...)
Cách hiꢐn thꢢ thông tin lên màn hình ñꢈ hꢉa:
Vùng ñꢊm màn hình hay còn gꢁi là bꢂ nhꢒ hiꢄn thꢚ ñưꢆc bꢞt ñꢖu tꢛ ñꢚa chꢡ
A000h:$0000h. Vì vꢍy, ñꢄ hiꢄn thꢚ thông tin ra màn hình thì ta chꢡ cꢖn ñưa thông tin
vào vùng ñꢊm màn hình bꢞt ñꢖu tꢛ ñꢚa chꢡ trên là ñưꢆc.
Có nhiꢈu cách ñꢄ vꢥ mꢂt ñiꢄm ra màn hình: có thꢄ dùng các phꢇc vꢇ cꢔa BIOS hoꢝc
cũng có thꢄ truy xuꢅt trꢃc tiꢋp vào vùng nhꢒ màn hình.
• Nꢋu dùng phꢇc vꢇ cꢔa BIOS, ta dùng hàm $0C ngꢞt $10:
Procedure PutPixel(Col,Row:Word; Color:Byte);
Var reg:Registers;
Begin
reg.ah:=$0C;
reg.al:=Color;
6
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
reg.bh:=0;
reg.cx:=Col;
reg.dx:=Row;
Intr($10,reg);
End;
• Nꢋu muꢓn truy xuꢅt trꢃc tiꢋp vào vùng ñꢊm màn hình: Giꢌ sꢙ mꢂt ñiꢄm (x,y)
ñưꢆc vꢥ trên màn hình vꢒi ñꢂ phân giꢌi 320x200x256 (mode 13h), ñiꢄm ñó sꢥ ñưꢆc
ñꢚnh vꢚ trong vùng ñꢊm bꢞt ñꢖu tꢛ ñꢚa chꢡ segment A000h và ñꢚa chꢡ offset ñưꢆc tính
theo công thꢑc: Offset = y*320 + x.
Ta có thꢄ viꢋt thꢔ tꢇc như sau:
Procedure PutPixel(x,y:Word; Color:Byte);
Var Offset:Word;
Begin
Offset:=(y shl 8) + (y shl 6) + x;
Mem[$A000:Offset]:=Color;
End;
1.3.2. Các biꢐu diꢣn tꢉa ñꢟ
Hꢖu hꢋt các chương trình ñꢀ hꢁa ñꢈu dùng hꢊ tꢁa ñꢂ Decartes (Hình 1.1).
Ta biꢋn ñꢗi:
O
MaxX
Y
Y
O
X
X
MaxY
Tꢁa ñꢂ thꢋ giꢒi thꢃc
Tꢁa ñꢂ thiꢋt bꢚ màn hình.
Hình 1.1
1.3.3. ðoꢝn thꢤng
Trong các hꢊ thꢓng ñꢀ hꢁa, các ñoꢘn thꢤng ñưꢆc biꢄu thꢚ bꢏi viꢊc “tô” ñoꢘn thꢤng
bꢞt ñꢖu tꢛ ñiꢄm ñꢖu mút này kéo dài cho ñꢋn khi gꢝp ñiꢄm ñꢖu mút kia.
1.4. CÁC THUꢕT TOÁN Vꢥ ðOꢦN THꢧNG
7
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
1.4.1. Bài toán: Vꢥ ñoꢘn thꢤng ñi qua 2 ñiꢄm A(x1,y1) và B(x2,y2)
* Trưꢐng hꢆp x1=x2 hoꢝc y1=y2: rꢅt ñơn giꢌn.
* Trưꢐng hꢆp ñưꢐng thꢤng có hꢊ sꢓ góc m:
Ý tưꢀng:
Vì các Pixel ñưꢆc vꢥ ꢏ các vꢚ trí nguyên nên ñưꢐng thꢤng ñưꢆc vꢥ giꢓng như hình
bꢍc thang (do làm tròn).
Vꢅn ñꢈ ñꢝt ra là chꢁn các tꢁa ñꢂ nguyên gꢖn vꢒi ñưꢐng thꢤng nhꢅt.
1.4.2. Thuꢎt toán DDA (Digital differential analyzer)
Xét ñưꢐng thꢤng có hꢊ sꢓ góc 0<m≤1(giꢌ sꢙ ñiꢄm ñꢖu A nꢕm bên trái và ñiꢄm cuꢓi
B nꢕm bên phꢌi). Nꢋu ta chꢁn ∆x=1và tính giá trꢚ y kꢋ tiꢋp như sau:
yk+1 = yk + ∆y = yk + m.∆x
= yk + m
Vꢒi hꢊ sꢓ góc m>1: ta hoán ñꢗi vai trò cꢔa x,y cho nhau. Nꢋu chꢁn ∆y=1 thì:
xk+1 = xk + 1/m
Tương tꢃ, nꢋu ñiꢄm B nꢕm bên trái và A nꢕm bên phꢌi thì:
yk+1 = yk - m
(0<m≤1, ∆x= -1)
(m>1, ∆y= -1)
xk+1 = xk - 1/m
Tóm lꢝi: Ta có thuꢍt toán vꢥ ñưꢐng thꢤng DDA như sau:
ꢀ Nhꢍp A(x1,y1) B(x2,y2)
ꢀ Tính ∆x = x2 - x1 ∆y = y2 - y1
ꢀ Khꢏi tꢘo các giá trꢚ:
Step = Max(|∆x| , |∆y|)
IncX = ∆x/Step;
x = x1; y = y1;
IncY = ∆y/Step; {bưꢒc tăng khi vꢥ}
{Chꢁn ñiꢄm vꢥ ñꢖu tiên}
Vꢥ ñiꢄm (x,y);
ꢀ Cho i chꢘy tꢛ 1 ñꢋn Step:
ꢁ
ꢁ
x = x + IncX;
y = y + IncY;
Vꢥ ñiꢄm (Round(x),Round(y))
Tꢛ ñó ta có thꢔ tꢇc vꢥ ñoꢘn thꢤng theo thuꢍt toán DDA như sau:
Procedure DDALine(x1,y1,x2,y2:Integer);
var dx,dy,step,i:integer;
8
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
xInc,yInc,x,y:real;
Begin
dx:=x2-x1; dy:=y2-y1;
If abs(dx)>abs(dy) Then step:=abs(dx)
else step:=abs(dy);
xInc:=dx/step;
yInc:=dy/step;
x:=x1;
y:=y1;
Putpixel(round(x),round(y),15);
for i:=1 to step do
Begin
x:=x+xInc;
y:=y+yInc;
Putpixel(round(x),round(y),15);
End;
End;
1.4.3. Thuꢎt toán Bresenham
Phương trình ñưꢐng thꢤng có thꢄ phát
biꢄu dưꢒi dꢘng: y = m.x + b (1)
Phương trình ñưꢐng thꢤng qua 2 ñiꢄm:
yi+
1
y
x − x1
y − y1
=
(*)
x2 − x1
y2 − y1
yi
ðꢝt ∆x = x2 - x1
∆y = y2 - y1
∆y
xi
xi+1
Hình 1.2
∆y
∆x
(*)
y = x.
+ y1 - x1.
∆x
∆y
Suy ra m =
nên ∆y = m. ∆x
(2)
(3)
∆x
b = y1 - m.x1
Ta chꢡ xét trưꢐng hꢆp hꢊ sꢓ góc 0<m<1.
Giꢌ sꢙ ñiꢄm (xi,yi) ñã ñưꢆc vꢥ. Ta phꢌi chꢁn ñiꢄm kꢋ tiꢋp là:
9
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
(xi + 1,yi) hoꢝc (xi +1,yi +1) (Xem hình 1.2)
Xét khoꢌng cách giꢎa 2 ñiꢄm chꢁn vꢒi ñiꢄm nꢕm trên ñưꢐng thꢃc. Nꢋu khoꢌng
cách nào bé hơn thì ta lꢅy ñiꢄm ñó.
ðꢝt:
d1 = y - yi = m.(xi +1) + b - yi
d2 = (yi +1) - y = yi + 1 - m.(xi + 1) - b
Suy ra:
d1 - d2 = 2m.(xi + 1) - 2yi + 2b - 1
∆y
= 2.
.(xi + 1) - 2yi + 2b - 1
∆x
∆x(d1 - d2) = 2∆y.xi - 2∆x.yi + 2∆y + ∆x.(2b - 1)
ðꢝt pi = ∆x(d1 - d2) và C = 2∆y + ∆x.(2b - 1)
thì pi = 2∆y.xi - 2∆x.yi + C
(4)
pi+1 = 2∆y.xi+1 - 2∆x.yi+1 + C
Suy ra:
pi+1 - pi = 2∆y(xi+1 - xi) - 2∆x(yi - yi+1)
= 2∆y - 2∆x(yi+1 - yi)
(5)
( vì xi+1 - xi = 1 )
* Nhꢆn xét:
. Nꢋu pi < 0: Chꢁn yi+1 = yi Tꢛ (5) ⇒ pi+1 = pi + 2∆y.
(d1<d2)
. Nꢋu pi ≥ 0: Chꢁn yi+1 = yi + 1 Tꢛ (5) ⇒ pi+1 = pi + 2∆y - 2∆x. (d1>d2)
Vꢒi ñiꢄm mút ñꢖu tiên, theo (4) ta có:
p1 = 2∆y.x1 - 2∆x.y1 + 2∆y + ∆x[2.(y1 - m.x1) - 1] = 2∆y - ∆x
Tꢛ ñó, ta có thꢄ tóm tꢞt thuꢍt toán vꢥ ñưꢐng thꢤng theo Bresenham cho trưꢐng hꢆp hꢊ
sꢓ góc 0<m<1 như sau:
• 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: ðiꢄm ñưꢆc chꢁn ñꢄ vꢥ ñꢖu tiên là (x1,y1).
• Bưꢊc 3: Tính ∆x = |x2 - x1| , ∆y = |y2 - y1| và P1 = 2∆y - ∆x
Nꢋu pi < 0 thì ñiꢄm kꢋ tiꢋp là (xi + 1,yi)
Ngưꢆc lꢘi: ñiꢄm kꢋ tiꢋp là (xi + 1,yi + 1)
10
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
• Bưꢊc 4: Tiꢋp tꢇc tăng x lên 1 Pixel. ꢠ vꢚ trí xi +1, ta tính:
pi+1 = pi + 2∆y nꢋu pi < 0
pi+1 = pi + 2.( ∆y - ∆x) nꢋu pi ≥ 0
Nꢋu pi+1 < 0 thì ta chꢁn toꢘ ñꢂ y kꢋ tiꢋp là yi+1
Ngưꢆc lꢘi thì ta chꢁn yi+1 +1
• Bưꢊc 5: Lꢝp lꢘi bưꢒc 4 cho ñꢋn khi x = x2.
Sau ñây là thꢔ tꢇc cài ñꢝt thuꢍt toán:
Procedure LINE(x1,y1,x2,y2:integer); { 0<m<1}
var dx,dy,x,y,p,c1,c2,xMax:integer;
Begin
dx:=abs(x1-x2);
dy:=abs(y1-y2);
c1:=2*dy;
c2:=2*(dy-dx);
p:=2*dy-dx;
if x1>x2 then
begin
x:=x2; y:=y2; xMax:=x1;
end
else
begin
x:=x1;y:=y1;xMax:=x2;
end;
putpixel(x,y,red);
while x<xMax do
begin
x:=x+1;
if p<0 then p:=p+c1
else begin
y:=y+1;
p:=p+c2;
end;
11
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
putpixel(x,y,red);
end;
end;
1.4.4. Thuꢎt toán MidPoint
Ta chꢡ xét trưꢐng hꢆp hꢊ sꢓ góc 0<m<1.
Thuꢍt toán này ñưa ra cách chꢁn ñiꢄm S(xi+1,yi) hay P(xi+1,yi+1) bꢕng cách so
sánh ñiꢄm thꢃc Q(xi+1,y) vꢒi ñiꢄm M (trung ñiꢄm cꢔa S và P).
ꢀ Nꢋu ñiꢄm Q nꢕm dưꢒi ñiꢄm M thì chꢁn ñiꢄm S
ꢀ Ngưꢆc lꢘi, chꢁn ñiꢄm P. (Xem hình 1.3)
Ta có dꢘng tꢗng quát cꢔa phương trình ñưꢐng thꢤng:
Ax + By + C = 0
vꢒi A = y2 – y1 , B = –(x2 – x1) ,
C = x2.y1 – x1.y2
ðꢝt F(x,y) = Ax + By + C, 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 hay P ñưꢆc ñưa vꢈ viꢊc xét dꢅu cꢔa:
1
pi = F(M) = F(xi + 1,yi + )
2
ꢀ Nꢋu pi < 0 ⇒ M nꢕm trên ñoꢘn
thꢤng ⇒ Q nꢕm dưꢒi M ⇒ Chꢁn S
P
yi+
ꢀ Nꢋu pi ≥ 0 ⇒ M nꢕm dưꢒi ñoꢘn
Q
M
1
thꢤng ⇒ Q nꢕm trên M ⇒ Chꢁn P
Mꢝt khác:
S
yi
1
pi = F(xi + 1,yi + )
2
xi
1
pi+1 = F(xi+1 + 1,yi+1 + )
2
Hình 1.3
nên
1
1
pi+1 - pi = F(xi+1 + 1,yi+1 + ) - F(xi + 1,yi + )
2
2
12
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
1
1
= A(xi+1+1) + B(yi+1 + ) + C - A(xi+1) - B(yi + ) - C
2
2
= A(xi+1 - xi) + B(yi+1 - yi)
= A + B(yi+1 - yi) (vì xi+1 - xi =1)
Suy ra:
pi+1 = pi + A + B(yi+1 - yi)
*Nhꢆn xét:
. Nꢋu pi < 0: Chꢁn ñiꢄm S: yi+1 = yi
(*)
Tꢛ (*) suy ra pi+1 = pi + A
. Nꢋu pi ≥ 0: Chꢁn ñiꢄm P: yi+1 = yi + 1 Tꢛ (*) suy ra pi+1 = pi + A + B
Vꢒi ñiꢄm mút ñꢖu tiên, ta có:
1
1
p1 = F(x1 + 1,y1 + ) = A(x1+1) + B(y1 + ) + C
2
2
B
B
= Ax1 + Bx1 + C + A +
= A +
(vì Ax1 + Bx1 + C = 0)
2
2
Thuꢁt toán MidPoint cho kꢂt quꢃ tương tꢄ như thuꢁt toán Bresenham.
1.5. THUꢕT TOÁN Vꢥ ðƯꢨNG TRÒN
Xét ñưꢐng tròn (C) tâm O(xc,yc) bán kính R.
(-
(y,x
Phương trình tꢗng quát cꢔa ñưꢐng tròn có dꢘng:
(x - xc)2 + (y - yc)2 = R2
(*)
(1)
(-
(x,y
y = yc ± R2 − (x − xC )2
(x,-
(-x,-
ðꢄ ñơn giꢌn thuꢍt toán, ñꢖu tiên ta xét ñưꢐng
tròn có tâm ꢏ gꢓc tꢁa ñꢂ (xc=0 và yc=0).
* Ý tưꢀng:
(-y,-
(
Hình
Do tính ñꢓi xꢑng cꢔa ñưꢐng tròn nên nꢋu ñiꢄm
(x,y) (C) thì các ñiꢄm (y,x), (-y,x), (-x,y), (-x,-y), (-y,-x), (y,-x), (x,-y) cũng (C) (Hình 1.4)
Vì vꢍy, ta chꢡ cꢖn vꢥ mꢂt phꢖn tám cung tròn rꢀi lꢅy ñꢓi xꢑng qua gꢓc O và 2 trꢇc toꢘ
ñꢂ thì ta có ñưꢆc toàn bꢂ ñưꢐng tròn.
1.5.1. Thuꢎt toán Bresenham
Giꢌ sꢙ (xi,yi) ñã vꢥ ñưꢆc. Cꢖn chꢁn ñiꢄm kꢋ tiꢋp là (xi +1,yi) hoꢝc (xi +1,yi -1)
(Hình 1.5)
Tꢛ phương trình: x2 + y2 = R2
ta tính ñưꢆc giá trꢚ y thꢃc ꢑng vꢒi xi +1 là:
13
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
y2 = R2 - (xi +1)2
ðꢝt: d1 = yi2 - y2 = yi2 - R2 + (xi + 1)2
d2 = y2 - (yi - 1)2 = R2 - (xi + 1)2 - (yi - 1)2
Suy ra:
pi = d1 - d2 = 2.(xi + 1)2 + yi2 + (yi - 1)2 - 2R2
⇒ pi+1 = 2.(xi+1 + 1)2 + y2i+1 + (yi+1 - 1)2 - 2R2
Tꢛ (2) và (3) ta có:
yi
y
yi-
1
(2)
(3)
xi
pi+1 - pi = 4xi + 6 + 2.(y2i+1 - yi2) - 2.(yi+1 - yi)
⇒ pi+1 = pi + 4xi + 6 + 2.(y2i+1 - yi2) - 2.(yi+1 - yi)
Hình
(4)
* Nhꢆn xét:
Nꢋu pi < 0: chꢁn yi+1 = yi
(4) ⇒ pi+1 = pi + 4xi + 6
Nꢋu pi ≥ 0: chꢁn yi+1 = yi - 1 (4) ⇒ pi+1 = pi + 4.(xi - yi) + 10
Ta chꢁn ñiꢄm ñꢖu tiên cꢖn vꢥ (0,R), theo (2) ta có: p1 = 3 - 2R
Tóm lꢀi: Ta có thuꢍt toán vꢥ ñưꢐng tròn:
• Bưꢊc 1: Chꢁn ñiꢄm ñꢖu cꢖn vꢥ (x1,y1) = (0,R)
• Bưꢊc 2: Tính P ñꢖu tiên: p1 = 3 - 2R
Nꢋu p < 0: chꢁn ñiꢄm kꢋ tiꢋp là (xi +1,yi). Ngưꢆc lꢘi chꢁn ñiꢄm (xi + 1,yi - 1)
• Bưꢊc 3: x:=x + 1, tính lꢘi p:
Nꢋu pi < 0: pi+1 = pi + 4xi + 6. Ngưꢆc lꢘi: pi+1 = pi + 4.(xi - yi) + 10
Khi ñó:
Nꢋu pi+1 < 0: chꢁn ñiꢄm kꢋ tiꢋp là (xi +1,yi+1). Ngưꢆc lꢘi chꢁn ñiꢄm (xi+1,yi+1-1)
• Bưꢊc 4: Lꢝp lꢘi bưꢒc 3 cho ñꢋn khi x = y.
Sau ñây là thꢔ tꢇc ñꢄ cài ñꢝt thuꢍt toán:
Procedure Circle(x0,y0,r:Integer);
Var p,x,y:Integer;
Procedure VeDiem;
Begin
PutPixel( x0 + x , y0 + y , color);
PutPixel( x0 - x , y0 + y , color);
PutPixel( x0 + x , y0 - y , color);
PutPixel( x0 - x , y0 - y , color);
14
Chương I. Các yꢖu tꢗ cơ sꢘ cꢙa ñꢈ hꢉa
PutPixel( x0 + y , y0 + x , color);
PutPixel( x0 - y , y0 + x , color);
PutPixel( x0 + y , y0 - x , color);
PutPixel( x0 - y , y0 - x , color);
End;
Begin
x:=0; y:=r;
p:=3 - 2*r;
While x<=y do
Begin
VeDiem;
If p<0 then p:=p + 4*x + 6
Else
Begin
p:=p + 4*(x-y) + 10;
y:=y-1;
End;
x:=x+1;
End;
End;
1.5.2. Thuꢎt toán MidPoint
Tꢛ phương trình ñưꢐng tròn: x2 + y2 = R2
ðꢝt F(x,y) = x2 + y2 - R2 ,ta có:
< 0 nꢋu (x,y) ꢏ trong ñưꢐng tròn
S
yi
M
Q
P
yi-
1
F(x,y)
= 0 nꢋu (x,y) ꢏ trên ñưꢐng tròn
> 0 nꢋu (x,y) ꢏ ngoàiñưꢐng tròn
xi
xi+1
Lúc này, viꢊc chꢁn các ñiꢄm S(xi+1,yi) hay
P(xi+1,yi-1) ñưꢆc ñưa vꢈ viꢊc xét dꢅu cꢔa:
Hình
1
pi = F(M) = F(xi + 1,yi - ) (Hình 1.6)
2
ꢀ Nꢋu pi < 0 ⇒ M nꢕm trong ñưꢐng tròn ⇒ Q gꢖn S hơn ⇒ Chꢁn S
ꢀ Nꢋu pi ≥ 0 ⇒ M nꢕm ngoài ñưꢐng tròn ⇒ Q gꢖn P hơn ⇒ Chꢁn P
15
Tải về để xem bản đầy đủ
146 trang
21660
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết đồ họa", để 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:
- giao_trinh_ly_thuyet_do_hoa.pdf
Do hoc may tinh-GD Tu xa.rar
