Bài giảng Đồ họa

Nội dung text: Bài giảng Đồ họa

1. Bài giảng Đồ họa
2. ÑOÀ HOÏA MAÙY TÍNH TTooånångg qquuaann vveeàà ññooà à hhooïaïa mmaaùùyy ttíínnhh Khaùùi nieääm · Ñoà hoïa maùy tính coù theå ñöôïc hieåu nhö laø taát caû nhöõng gì lieân quan ñeán vieäc taïo ra aûnh (image) baèng maùy tính. Chuùng bao goàm : taïo, löu tröõ, thao taùc treân caùc moâ hình (model) vaø caùc aûnh. · Thuaät ngöõ ñoà hoïa maùy tính (computer graphics) do William Fetter ñaët ra naêm 1960 ñeå moâ taû moät caùch thieát keá môùi khi ñang laøm vieäc taïi haõng Boeing. · Vôùi caùch naøy, anh ta ñaõ taïo nhieàu aûnh coù theå söû duïng laïi ñeå coù theå deã daøng thieát keá buoàng laùi cuûa phi coâng theo yù muoán. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 1/14
3. ÑOÀ HOÏA MAÙY TÍNH Moäät soáá öùùng duïïng cuûûa ñoà à hoïïa maùyù tính · Hoã trôï thieát keá (CAD - Computer Aided Design) Goàm hai böôùc chính ¨ Phaùc thaûo cuûa phaàn khung(wireframe outline) maø töø ñoù coù theå thaáy ñöôïc toaøn boä hình daïng vaø caùc thaønh phaàn beân trong cuûa caùc ñoái töôïng. Söû duïng kó thuaät naøy, ngöôøi thieát keá seõ deã daøng nhaän thaáy ngay caùc thay ñoåi cuûa ñoái töôïng khi tieán haønh hieäu chænh caùc chi tieát hay thay ñoåi goùc nhìn, . ¨ Keát hôïp caùc moâ hình chieáu saùng, toâ maøu vaø taïo boùng beà maët ñeå taïo ra keát quaû cuoái cuøng raát gaàn vôùi theá giôùi thöïc. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 2/14
4. ÑOÀ HOÏA MAÙY TÍNH · Visualization ¨ Duøng phaùt sinh caùc bieåu ñoà, ñoà thò, trong vieäc minh hoïa moái quan heä giöõa nhieàu ñoái töôïng vôùi nhau. ¨ Toùm löôïc caùc döõ lieäu veà taøi chính, thoáng keâ, kinh teá, khoa hoïc, toaùn hoïc, giuùp cho vieäc nghieân cöùu, quaûn lí, moät caùch coù hieäu quaû. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 3/14
5. ÑOÀ HOÏA MAÙY TÍNH · Giaûi trí · Taïo giao dieän Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 4/14
6. ÑOÀ HOÏA MAÙY TÍNH Toåång quan veàà moäät heä ä ñoàà hoïaï · Caùc thaønh phaàn phaàn cöùng ¨ Thieát bò hieån thò : maøn hình, maùy in, ¨ Thieát bò nhaäp : baøn phím, chuoät, · Caùc coâng cuï phaàn meàm ¨ Coâng cuï öùng duïng (application package) : Ñöôïc thieát keá cho caùc ngöôøi söû duïng ñeå taïo ra caùc hình aûnh maø khoâng caàn quan taâm tôùi caùc thao taùc beân trong hoaït ñoäng nhö theá naøo. Ví duï : AutoCAD, Adobe Photoshop, 3D Studio, ¨ Coâng cuï laäp trình (programming package) : Cung caáp moät taäp caùc haøm ñoà hoïa coù theå ñöôïc duøng trong caùc ngoân ngöõ laäp trình caáp cao nhö C, Pascal, Ví duï : GRAPH.TPU, GRAPHICS.LIB, Open GL, · Caùc chuaån phaàn meàm ¨ Ra ñôøi ñeå ñaùp öùng tính töông thích : Neáu caùc phaàn meàm ñöôïc thieát keá vôùi caùc haøm ñoà hoïa chuaån chuùng coù theå duøng ñöôïc cho nhieàu heä phaàn cöùng vaø moâi tröôøng laøm vieäc khaùc nhau. ¨ GKS (Graphics Kernel System) laø chuaån ra ñôøi ñaàu tieân cho vieäc phaùt trieån caùc phaàn meàm ñoà hoïa. Ban ñaàu GKS ñöôïc thieát keá chæ duøng cho taäp caùc coâng cuï ñoà hoïa hai chieàu, sau ñoù môùi ñöôïc môû roäng ra cho ñoà hoïa ba chieàu. ¨ Caùc haøm cuûa GKS thöïc söï chæ laø caùc moâ taû tröøu töôïng, ñoäc laäp vôùi baát kì ngoân ngöõ laäp trình naøo. Ñeå caøi ñaët moät chuaån ñoà hoïa cho ngoân ngöõ cuï theå naøo, caùc cuù phaùp töông öùng seõ ñöôïc xaùc ñònh vaø cuï theå hoùa. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 5/14
7. ÑOÀ HOÏA MAÙY TÍNH · Caùc thaønh phaàn cuûa coâng cuï laäp trình ¨ Taäp caùc coâng cuï taïo ra caùc ñoái töôïng ñoà hoïa cô sôû nhö ñieåm, ñoaïn thaúng, ñöôøng cong, vuøng toâ, kí töï, ¨ Taäp caùc coâng cuï thay ñoåi thuoäc tính cuûa caùc ñoái töôïng cô sôû keå treân nhö maøu saéc, kieåu ñöôøng, kieåu chöõ, maãu toâ ¨ Taäp caùc coâng cuï thöïc hieän caùc pheùp bieán ñoåi hình hoïc duøng ñeå thay ñoåi kích thöôùc, vò trí, höôùng, ¨ Taäp caùc coâng cuï bieán ñoåi heä quan saùt duøng ñeå xaùc ñònh vò trí quan saùt cuûa caùc ñoái töôïng vaø vò trí treân thieát bò hieån thò ñoái töôïng. ¨ Taäp caùc coâng cuï nhaäp lieäu : caùc öùng duïng ñoà hoïa coù theå söû duïng nhieàu loaïi thieát bò nhaäp khaùc nhau nhö chuoät, baøn phím, buùt veõ, baûng, ñeå ñieàu khieån vaø xöû lí doøng döõ lieäu nhaäp. ¨ Taäp caùc coâng cuï chöùa caùc thao taùc duøng cho quaûn lí vaø ñieàu khieån nhö khôûi taïo vaø ñoùng cheá ñoä ñoà hoïa, xoùa toaøn boä maøn hình, Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 6/14
8. ÑOÀ HOÏA MAÙY TÍNH Hai moâ â hình cô baûûn cuûûa öùùng duïïng ñoàà hoïaï · Öùng duïng ñoà hoïa döïa treân maãu soá hoùa (sampled- based graphics) ¨ Caùc pixel (ñieåm aûnh) ñöôïc taïo ra bôûi thao taùc soá hoùa aûnh baèng caùch söû duïng caùc chöông trình veõ döïa treân maãu soá hoùa hay maùy queùt. ¨ Caùc öùng duïng thuoäc daïng naøy goàm : PaintBrush, Adobe Photoshop, · Öùng duïng ñoà hoïa döïa treân ñaëc tröng hình hoïc (geometry-based graphics) ¨ Duøng caùc ñaëc tröng hình hoïc vaø caùc thuoäc tính ñeå moâ taû ñoái töôïng. Sau ñoù caùc ñoái töôïng seõ ñöôïc soá hoùa ñeå phuïc vuï cho hieån thò. ¨ Caùc öùng duïng thuoäc daïng naøy : Adobe Illustrator, AutoCAD, Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 7/14
9. ÑOÀ HOÏA MAÙY TÍNH Öùùng duïïng ñoàà hoïïa döïïa treâân maããu soáá hoùùa · Caùc ñoái töôïng ñoà hoïa ñöôïc taïo ra bôûi löôùi caùc pixel rôøi raïc. · Caùc pixel naøy coù moät moâ taû veà toïa ñoä ñeå xaùc ñònh vò trí vaø giaù trò maãu (sample values), thoâng thöôøng laø ñoä saùng hay maøu saéc. · Caùc pixel naøy coù theå ñöôïc taïo ra baèng caùc chöông trình veõ, maùy queùt, · Khi moät aûnh ñöôïc xaùc ñònh bôûi taäp caùc pixel, chuùng coù theå coù caùc thao taùc : ¨ Bieân taäp aûnh (image editting) : caét, daùn caùc vuøng treân aûnh, söû duïng caùc coâng cuï toâ maøu ñeå hieäu chænh, ¨ Xöû lí aûnh (image processing) : söû duïng caùc thuaät toaùn ñeå thay ñoåi aûnh maø khoâng coù söï can thieäp cuûa ngöôøi duøng, bao goàm : laøm nhoøe aûnh (blurring), laøm neùt aûnh (sharpening), doø ñöôøng bieân (edge-detection), caân chænh maøu saéc, · Moät soá thuaän lôïi ¨ Deã daøng thay ñoåi aûnh baèng caùch thay ñoåi maøu saéc hay vò trí cuûa caùc pixel, ví duï nhö laáy aûnh aâm baûn, ¨ Coù theå di chuyeån caùc vuøng aûnh töø nôi naøy sang nôi khaùc deã daøng. · Moät soá baát lôïi ¨ Khoâng theå xem xeùt ñoái töôïng töø caùc goùc nhìn khaùc nhau. ¨ Hieäu chænh veà thuoäc tính hình hoïc, kích thöôùc phöùc taïp. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 8/14
10. ÑOÀ HOÏA MAÙY TÍNH Öùùng duïïng ñoàà hoïïa döïïa treâân ñaëëc tröng hình hoïïc · Caùc ñoái töôïng ñoà hoïa cô sôû nhö ñoaïn thaúng, ña giaùc, ñöôïc löu tröõ baèng caùc moâ hình (model) vaø caùc thuoäc tính (attribute) cuûa chuùng. ¨ Caùc moâ hình thöïc chaát laø caùc moâ taû toaùn hoïc, ví duï ñoaïn thaúng ñöôïc moâ hình baèng hai ñieåm ñaàu, cuoái, ¨ Caùc thuoäc tính ñöôïc duøng ñeå moâ taû caùch maø caùc ñoái töôïng ñöôïc hieån thò ví duï nhö maøu saéc, ñoä daøy, · Caùc aûnh ñöôïc taïo bôûi taäp caùc pixel thoâng qua vieäc soá hoùa caùc ñaëc tröng hình hoïc phuïc vuï cho moãi yeâu caàu hieån thò. Caùc aûnh coù theå khaùc nhau tuøy vaøo moãi yeâu caàu hieån thò khaùc nhau, nhöng ñeàu xuaát phaùt töø moät moâ hình. · Ngöôøi duøng khoâng thao taùc tröïc tieáp vôùi töøng pixel cuûa öùng duïng daïng naøy maø thao taùc treân caùc thaønh phaàn hình hoïc cuûa ñoái töôïng, sau ñoù soá hoùa laïi roài môùi hieån thò. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 9/14
11. ÑOÀ HOÏA MAÙY TÍNH TThhiieeátát bbòò hhiieeånån tthhòò :: MMaaønøn hhììnnhh Caááu taïïo cuûûa CRT · Moät chuøm caùc tia ñieän töû (tia aâm cöïc) phaùt ra töø moät suùng ñieän töû, vöôït qua caùc heä thoáng hoäi tuï (focusing) vaø daãn höôùng (deflection) seõ höôùng tôùi caùc vò trí xaùc ñònh treân maøn hình ñöôïc phuû moät lôùp phosphor. · Taïi moãi vò trí töông taùc vôùi tia ñieän töû, haït phosphor seõ phaùt ra moät chaám saùng nhoû. Vì aùnh saùng phaùt ra bôûi caùc haït phosphor môø daàn raát nhanh neân caàn phaûi coù moät caùch naøo ñoù ñeå duy trì aûnh treân maøn hình. Moät trong caùc caùch ñoù laø laëp ñi laëp laïi nhieàu laàn vieäc veõ laïi aûnh thaät nhanh baèng caùch höôùng caùc tia ñieän töû trôû laïi vò trí cuõ. Kieåu hieån thò naøy goïi laø refresh CRT. · Coù nhieàu loaïi phosphor ñöôïc duøng trong moät CRT. Ngoaøi maøu saéc ra, ñieåm khaùc nhau chính giöõa caùc loaïi phosphor laø “ñoä beàn“ (persistent), ñoù laø khoaûng thôøi gian phaùt saùng sau khi tia CRT khoâng coøn taùc ñoäng. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 10/14
12. ÑOÀ HOÏA MAÙY TÍNH · Lôùp phosphor coù ñoä beàn thaáp caàn toác ñoä laøm töôi cao hôn ñeå giöõ cho hình aûnh treân maøn hình khoûi nhoøe. Loaïi naøy thöôøng raát toát cho hoaït hình, raát caàn thay ñoåi hình aûnh lieân tuïc. Lôùp phosphor coù ñoä beàn cao thöôøng ñöôïc duøng cho vieäc hieån thò caùc aûnh tónh, ñoä phöùc taïp cao. Maëc duø moät soá loaïi phosphor coù ñoä beàn lôùn hôn 1 giaây, tuy nhieân caùc maøn hình ñoà hoïa thöôøng ñöôïc xaây döïng vôùi ñoä beàn dao ñoäng töø 10 ñeán 60 micro giaây. · Soá löôïng toái ña caùc ñieåm coù theå hieån thò treân moät CRT ñöôïc goïi laø ñoä phaân giaûi (resolution). · Kích thöôùc vaät lí cuûa maøn hình ñoà hoïa ñöôïc tính töø ñoä daøi cuûa ñöôøng cheùo maøn hình, thöôøng dao ñoäng töø 12 ñeán 27 inch hoaëc lôùn hôn. Moät maøn hình CRT coù theå ñöôïc keát hôïp vôùi nhieàu loaïi maùy khaùc nhau, do ñoù soá löôïng caùc ñieåm treân maøn hình coù theå ñöôïc veõ thaät söï coøn tuøy thuoäc vaøo khaû naêng cuûa heä thoáng maø noù keát hôïp vaøo. · Tæ soá phöông laø tæ leä cuûa caùc ñieåm doïc vaø caùc ñieåm ngang caàn ñeå phaùt sinh caùc ñoaïn thaúng coù ñoä daøi ñôn vò theo caû hai höôùng treân maøn hình (trong moät soá tröôøng hôïp ngöôøi ta thöôøng duøng tæ soá phöông nhö laø tæ soá cuûa caùc ñieåm theo chieàu ngang so vôùi caùc ñieåm theo chieàu doïc). Vôùi caùc maøn hình coù tæ soá phöông khaùc 1, deã daøng nhaän thaáy laø caùc hình vuoâng hieån thò treân noù seõ coù daïng hình chöõ nhaät, caùc hình troøn seõ coù daïng hình ellipse. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 11/14
13. ÑOÀ HOÏA MAÙY TÍNH Maøøn hình daïïng ñieååm (raster - scan display): · Chuøm tia ñieän töû seõ ñöôïc queùt ngang qua maøn hình, moãi laàn moät doøng vaø queùt tuaàn töï töø treân xuoáng döôùi. Söï baät taét cuûa caùc ñieåm saùng treân maøn hình phuï thuoäc vaøo cöôøng ñoä cuûa tia ñieän töû vaø ñaây chính laø cô sôû cuûa vieäc taïo ra hình aûnh treân maøn hình. · Moãi ñieåm treân maøn hình ñöôïc goïi laø moät pixel. Caùc thoâng tin veà hình aûnh hieån thò treân maøn hình ñöôïc löu tröõ trong moät vuøng boä nhôù goïi laø vuøng ñeäm laøm töôi (refresh buffer) hay laø vuøng ñeäm khung (frame buffer). Vuøng boä nhôù naøy löu tröõ taäp caùc giaù trò cöôøng ñoä saùng cuûa toaøn boä caùc ñieåm treân maøn hình vaø luoân luoân toàn taïi moät song aùnh giöõa moãi ñieåm treân maøn hình vaø moãi phaàn töû trong vuøng naøy. · Ñeå thay ñoåi caùc hình aûnh caàn hieån thò, caùc giaù trò töông öùng vôùi vò trí vaø ñoä saùng phaûi ñöôïc ñaët vaøo vuøng ñeäm khung. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 12/14
14. ÑOÀ HOÏA MAÙY TÍNH · Ñeå taïo ra caùc aûnh ñen traéng, ñôn giaûn chæ caàn löu thoâng tin cuûa moãi pixel baèng 1 bit (caùc giaù trò 0, 1 seõ töôïng tröng cho vieäc taét (toái), baät (saùng) pixel treân maøn hình). Trong tröôøng hôïp aûnh nhieàu maøu, ngöôøi ta caàn nhieàu bit hôn, neáu thoâng tin cuûa moãi pixel ñöôïc löu baèng b bit, thì ta coù theå coù 2b giaù trò maøu phaân bieät cho pixel ñoù. · Trong caùc maøn hình maøu, ngöôøi ta ñònh nghóa taäp caùc maøu laøm vieäc trong moät baûng tra (LookUp Table - LUT). Moãi phaàn töû cuûa LUT ñònh nghóa moät boä ba giaù trò R (Red), G (Green), B (Blue) moâ taû moät maøu naøo ñoù. Khi caàn söû duïng moät maøu, ta chæ caàn chæ ñònh soá thöù töï (index) töông öùng cuûa maøu ñoù trong LUT. Baûng LUT coù theå ñöôïc thay ñoåi bôûi caùc öùng duïng vaø ngöôøi laäp trình coù theå can thieäp ñieàu khieån. Vôùi caùch laøm naøy chuùng ta coù theå tieát kieäm khoâng gian löu tröõ cho moãi phaàn töû trong vuøng ñeäm khung. · Soá phaàn töû cuûa LUT ñöôïc xaùc ñònh töø soá löôïng caùc bits/pixel. Neáu moãi phaàn töû cuûa vuøng ñeäm khung duøng b bits ñeå löu thoâng tin cuûa moät pixel, thì baûng LUT coù 2b phaàn töû. Neáu b=8, LUT seõ coù 28=256 phaàn töû, ñoù chính laø soá maøu coù theå ñöôïc hieån thò cuøng moät luùc treân maøn hình. · Vieäc laøm töôi treân maøn hình daïng naøy ñöôïc thöïc hieän ôû toác ñoä 60 ñeán 80 frame/giaây. Ñoâi khi toác ñoä laøm töôi coøn ñöôïc bieåu dieãn baèng ñôn vò Hertz (Hz – soá chu kì/ giaây), trong ñoù moät chu kì töông öùng vôùi moät frame. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 13/14
15. ÑOÀ HOÏA MAÙY TÍNH · Khi ñaït ñeán cuoái moãi doøng queùt, tia ñieän töû quay trôû laïi beân traùi cuûa maøn hình ñeå baét ñaàu doøng queùt keá tieáp. Vieäc quay trôû laïi phía traùi maøn hình sau khi laøm töôi moãi doøng queùt ñöôïc goïi laø tia hoài ngang (horizontal retrace). Vaø tôùi cuoái moãi frame, tia ñieän töû (tia hoài doïc – vertical retrace) quay trôû laïi goùc treân beân traùi cuûa maøn hình ñeå chuaån bò baét ñaàu frame keá tieáp. · Trong moät soá maøn hình, moãi frame ñöôïc hieån thò thaønh hai giai ñoaïn söû duïng kó thuaät laøm töôi ñan xen nhau (interlaced refesh). ÔÛ giai ñoaïn ñaàu tieân, tia queùt seõ queùt moät soá doøng töø treân xuoáng döôùi, sau tia hoài doïc, caùc doøng coøn laïi seõ ñöôïc queùt. Vieäc ñan xen caùc doøng queùt naøy cho pheùp chuùng ta thaáy ñöôïc toaøn maøn hình hieån thò chæ trong moät nöûa thôøi gian so vôùi duøng ñeå queùt taát caû caùc doøng moät laàn töø treân xuoáng döôùi. Kó thuaät naøy thöôøng ñöôïc duøng cho loaïi maøn hình coù toác ñoä laøm töôi thaáp. Döông Anh Ñöùc, Leâ Ñình Duy Toång quan veà Ñoà hoïa maùy tính 14/14
16. ÑOÀ HOÏA MAÙY TÍNH CCaaùùcc tthhuuaaätät ttooaaùnùn vveeõ õ ññööôôønøngg Daããn nhaäpä · 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ø (xi , yi ),i = 0, . Ñaây laø caùc ñieåm nguyeân seõ ñöôïc hieån thò treân maøn hình. · Baøi toaùn ñaët ra laø neáu bieát ñöôïc (xi , yi ) laø toïa ñoä nguyeân xaùc ñònh ôû böôùc thöù i, ñieåm nguyeân tieáp theo (xi+1 , yi+1 ) seõ ñöôïc xaùc ñònh nhö theá naøo. · Ñoái töôïng hieån thò treân löôùi nguyeân ñöôïc lieàn neùt, caùc ñieåm maø (xi+1 , yi+1 ) coù theå choïn chæ laø moät trong taùm ñieåm ñöôïc ñaùnh soá töø 1 ñeán 8 trong hình sau (ñieåm ñen chính laø (xi , yi )).Hay noùi caùch khaùc : (xi+1 , yi+1 ) = (xi ± 1, yi ± 1). 4 3 2 5 1 6 7 8 · 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ä. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 1/22
17. ÑOÀ HOÏA MAÙY TÍNH TThhuuaaätät ttooaaùnùn vveeõ õ ññööôôønøngg tthhaaúúnngg · Xeùt ñoaïn thaúng coù heä soá goùc 0 0 . · Vôùi caùc ñoaïn thaúng daïng naøy, neáu (xi , yi ) laø ñieåm ñaõ xaùc ñònh ñöôïc ôû böôùc thöù i (ñieåm maøu ñen) thì ñieåm caàn choïn (xi+1 , yi+1 ) ôû böôùc thöù (i+1) seõ laø moät trong hai tröôøng hôïp nhö hình veõ sau : ìxi+1 = xi + 1 í îyi+1 Î {yi , yi + 1} (xi+1, yi+1) 2 y (x +1, y ) i 1 i i xi · 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ä. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 2/22
18. ÑOÀ HOÏA MAÙY TÍNH Thuaäät toaùùn DDA (Digital Differential Analyzer) · Vieäc quyeát ñònh choïn yi+1 laø yi hay yi + 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 (xi + 1, y) thuoäc veà ñoaïn thaúng thöïc. Tieáp ñoù, yi+1 seõ laø giaù trò sau khi laøm troøn giaù trò tung ñoä y. y = m(xi + 1) + b · Nhö vaäy : yi+1 = Round(y) (xi+1, Round(y)) (xi+1, y) (xi, yi) · 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 : ysau = mxi+1 + b = m(xi + 1) + b ytröôùc = mxi + b Þ ysau = ytröôùc + m Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 3/22
19. ÑOÀ HOÏA MAÙY TÍNH Löu ñoà thuaät toaùn DDA Begin m=Dy/Dx; x=x1; y=y1; putpixel(x, Round(y), c); x<x2 No Yes x=x+1; y=y+m; putpixel(x, Round(y),c); End Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 4/22
20. ÑOÀ HOÏA MAÙY TÍNH · Ví duï : Cho A(12, 20) vaø B(22, 27), ta coù m= 0.7 ii xii yii y 0 12 20 20 1 13 21 20.7 2 14 21 21.4 3 15 22 22.1 4 16 5 17 6 18 7 19 8 20 9 21 10 22 27 · 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 Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 5/22
21. ÑOÀ HOÏA MAÙY TÍNH Thuaäät toaùùn Bresenham (xi+1, y) P yi+1 d2 y d1 S yi xi xi+1 · Goïi (xi + 1, y) laø ñieåm thuoäc ñoaïn thaúng. Ta coù: y = m(xi + 1) + b . d1 = y - yi · Ñaët d2 = (yi + 1) - y · Xeùt taát caû caùc vò trí töông ñoái cuûa y so vôùi yi vaø yi + 1 , vieäc choïn ñieåm (xi+1 , yi+1 ) laø S hay P phuï thuoäc vaøo vieäc so saùnh d1 vaø d2 hay daáu cuûa d1 - d2 : ¨ Neáu d1 - d2 < 0 , ta seõ choïn ñieåm S, töùc laø yi+1 = yi . ¨ Ngöôïc laïi, neáu d1 - d2 ³ 0 , ta seõ choïn ñieåm P, töùc laø yi+1 = yi + 1 · Xeùt pi = Dx(d1 - d2 ) = Dx(2y - 2yi - 1) Þ pi = Dx[2(m(xi + 1) + b) - 2yi - 1] Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 6/22
22. ÑOÀ HOÏA MAÙY TÍNH Dy m = · Thay Dx vaøo phöông trình treân ta ñöôïc : pi = 2Dyxi - 2Dxyi + c , vôùi c = 2Dy + (2b - 1)Dx . · Nhaän xeùt raèng neáu taïi böôùc thöù i ta xaùc ñònh ñöôïc daáu cuûa pi thì xem nhö ta xaùc ñònh ñöôïc ñieåm caàn choïn ôû böôùc (i+1). · Ta coù : pi+1 - pi = (2Dyxi+1 - 2Dxyi+1 + c) - (2Dyxi - 2Dxyi + c) Û pi+1 - pi = 2Dy(xi+1 - xi ) - 2Dx(yi+1 - yi ) Û pi+1 - pi = 2Dy - 2Dx(yi+1 - yi ), do xi+1 = xi + 1 · Töø ñaây ta coù theå suy ra caùch tính pi+1 töø pi nhö sau : ¨ Neáu pi < 0 thì pi+1 = pi + 2Dy do ta choïn yi+1 = yi . ¨ Ngöôïc laïi, neáu pi ³ 0 , thì pi+1 = pi + 2Dy - 2Dx , do ta choïn yi+1 = yi + 1 . · Giaù trò p0 ñöôïc tính töø ñieåm veõ ñaàu tieân (x0 , y0 ) theo coâng thöùc : p0 = 2Dyx0 - 2Dxy0 + c = 2Dyx0 - 2Dxy0 + 2Dy - (2b - 1)Dx · Do (x0 , y0 ) laø ñieåm nguyeân thuoäc veà ñoaïn thaúng Dy y = mx + b = x + b neân ta coù 0 0 Dx 0 . Theá vaøo phöông trình treân ta suy ra : p0 = 2Dy - Dx . Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 7/22
23. ÑOÀ HOÏA MAÙY TÍNH 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); x<x2 No Yes p<0 No Yes p=p+Const1; p=p+Const2; y=y+1 x=x+1; putpixel(x,y,c); End Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 8/22
24. ÑOÀ HOÏA MAÙY TÍNH · Ví duï : Cho A(12, 20) vaø B(22, 27), · Ta coù ¨ Dx = 22-12 = 10, Dy=27-20=7 ¨ Const1 = 2Dy = 14, Const2 = 2(Dy – Dx) = -6 ¨ p0 = 2Dy – Dx = 14-10 = 4 ii xii yii pii 0 12 20 4 1 13 21 -2 2 14 21 12 3 15 22 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 26 -4 9 21 26 10 10 22 27 4 · 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 pi ñeå quyeát ñònh ñieåm keá tieáp, vaø söû duïng coâng thöùc truy hoài pi+1 - pi ñeå tính pi baè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. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 9/22
25. ÑOÀ HOÏA MAÙY TÍNH · 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 = x2 - x1; Dy = y2 - y1; p = 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 Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 10/22
26. ÑOÀ HOÏA MAÙY TÍNH Thuaäät toaùùn MidPoint · Thuaät toaùn MidPoint ñöa ra caùch choïn yi+1 laø yi hay yi + 1 baèng caùch so saùnh ñieåm thöïc Q(xi + 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. ¨ Neáu ñieåm Q naèm treân ñieåm MidPoint ta choïn P. Q(xi+1, y) P yi+1 MidPoint S yi xi xi+1 · Ta coù daïng toång quaùt cuûa phöông trình ñöôøng thaúng : Ax + By + C = 0 vôùi A = y2 - y1 , B = -(x2 - x1 ), C = x2 y1 - x1 y2 · Ñaët F(x, y) = Ax + By + C , ta coù nhaän xeùt : ì 0,neáu (x, y) naèm phía döôùi ñöôøng thaúng. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 11/22
27. ÑOÀ HOÏA MAÙY TÍNH · Luùc naøy vieäc choïn caùc ñieåm S, P ôû treân ñöôïc ñöa veà æ 1 ö vieäc xeùt daáu cuûa pi = 2F(MidPoint ) = 2Fç xi +1, yi + ÷ . è 2 ø ¨ Neáu pi < 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ø yi+1 = yi . ¨ Ngöôïc laïi, neáu pi ³ 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ø yi+1 = yi + 1 . · Maët khaùc : æ 1 ö æ 1 ö pi+1 - pi = 2Fç xi+1 + 1, yi+1 + ÷ - 2Fç xi + 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 = 2A + 2B(yi+1 - yi ) = 2Dy - 2Dx(yi+1 - yi ) · Nhö vaäy : ¨ pi+1 = pi + 2Dy , neáu pi < 0 do ta choïn yi+1 = yi . ¨ pi+1 = pi + 2Dy - 2Dx , neáu pi ³ 0 do ta choïn yi+1 = yi + 1 . · Ta tính giaù trò p0 öùng vôùi ñieåm ban ñaàu (x0 , y0 ) , vôùi nhaän xeùt raèng (x0 , y0 ) laø ñieåm thuoäc veà ñoaïn thaúng, töùc laø coù : Ax0 + By0 + C = 0 æ 1 ö é æ 1 ö ù p0 = 2Fç x0 + 1, y0 + ÷ = 2êA(x0 + 1) + Bç y0 + ÷ + Cú è 2 ø ë è 2 ø û Þ p0 = 2(Ax0 + By0 + C) + 2A + B = 2A + B = 2Dy - Dx Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 12/22
28. ÑOÀ HOÏA MAÙY TÍNH Caââu hoûûi kieååm tra · Xeùt thuaät toaùn Bresenham, vôùi caùch ñaët d1 vaø d2 nhö treân, coù khi naøo d1 hay d2 aâm hay khoâng ? Cho ví duï minh hoïa. · Taïi sao phaûi so saùnh giaù trò pi vôùi 0 trong caùc thuaät toaùn MidPoint vaø Bresenham, baûn chaát cuûa vieäc so saùnh naøy laø gì ? · Taïi sao phaûi nhaân F(MidPoint) vôùi 2 khi gaùn cho pi theo coâng thöùc pi=2*F(MidPoint) ? Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 13/22
29. ÑOÀ HOÏA MAÙY TÍNH · Caøi ñaët thuaät toaùn cho tröôøng hôïp 0 £ m £ 1, Dx 0 ñaõ caøi ñaët coäng theâm moät soá thay ñoåi sau : ¨ Thay bieåu thöùc x=x+1 baèng x=x-1 vaø y=y+1 baèng y=y-1 vì trong tröôøng hôïp naøy x vaø y ñeàu giaûm daàn. ¨ Nhaän xeùt raèng khi p 0 vaø thay ñoåi moät soá ñieåm sau : v Neáu Dx<0 thì böôùc nhaûy cuûa x seõ thay baèng –1. Töông töï neáu Dy<0, böôùc nhaûy cuûa y cuõng seõ laø –1. v Thay Dx baèng abs(Dx), Dy=abs(Dy) trong taát caû caùc coâng thöùc coù chöùa Dx, Dy. ¨ Tröôøng hôïp m £ -1 hay m ³ 1 : v Thay ñoåi vai troø cuûa x vaø y, nghóa laø thay x baèng y, y baèng x, Dx baèng Dy, Dy baèng Dx trong taát caû caùc coâng thöùc. v Thöïc hieän nguyeân taéc veà böôùc nhaûy, thay ñoåi coâng thöùc Dx, Dy nhö trong tröôøng hôïp –1 £ m £ 1 Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 14/22
30. ÑOÀ HOÏA MAÙY TÍNH Veõõ ñöôøøng troøøn baèèng 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 (C1/8) laø cung 1/8 ñöôøng troøn, sau ñoù laáy ñoái xöùng. Cung (C1/8) ñöôïc moâ taû nhö sau (cung cuûa phaàn toâ xaùm trong hình veõ) : ì 2 ï0 £ x £ R ï 2 í ï 2 R £ y £ R îï 2 (-x,y) (x,y) (-y,x) (y,x) R (-y,-x) 2 (y,-x) (-x,-y) (x,-y) · Nhö vaäy neáu coù (x, y) Î (C1/8) thì caùc ñieåm : (y, x), (y,- x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) seõ thuoäc (C). Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 15/22
31. ÑOÀ HOÏA MAÙY TÍNH · Choïn ñieåm baét ñaàu ñeå veõ laø ñieåm (0,R). · Döïa vaøo hình veõ, neáu (xi , yi ) laø ñieåm nguyeân ñaõ tìm ñöôïc ôû böôùc thöù i, thì ñieåm (xi+1 , yi+1 ) ôû böôùc thöù (i+1) laø söï löïa choïn giöõa S vaø P. ìxi+1 = xi + 1 · Nhö vaäy : í îyi+1 Î {yi , yi - 1} Q(xi+1, y) S yi MidPoint P yi-1 xi xi+1 2 2 2 · Ñaët F(x, y) = x + y - R , ta coù : ì 0,neáu (x, y) naèm ngoaøi ñöôøng troøn. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 16/22
32. ÑOÀ HOÏA MAÙY TÍNH æ 1 ö pi = F(MidPoint) = Fç xi + 1, yi - ÷ · Xeùt è 2 ø . Ta coù : ¨ Neáu pi < 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ø yi+1 = yi . ¨ Ngöôïc laïi, neáu pi ³ 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ø yi+1 = yi - 1 . · Maët khaùc : æ 1 ö æ 1 ö pi+1 - pi = Fç xi+1 + 1, yi+1 - ÷ - Fç xi + 1, yi - ÷ è 2 ø è 2 ø é 2 ù é 2 ù 2 æ 1 ö 2 2 æ 1 ö 2 Û pi+1 - pi = ê(xi+1 + 1) + ç yi+1 - ÷ - R ú - ê(xi + 1) + ç yi - ÷ - R ú ëê è 2ø ûú ëê è 2ø ûú 2 2 Û pi+1 - pi = 2xi + 3 + (yi+1 - yi ) - (yi+1 - yi ) · Vaäy : ¨ pi+1 = pi + 2xi + 3 , neáu pi < 0 do ta choïn yi+1 = yi . ¨ pi+1 = pi + 2xi - 2yi + 5 , neáu pi ³ 0 do ta choïn yi+1 = yi - 1 . · p0 öùng vôùi ñieåm ban ñaàu (x0 , y0 ) = (0, R) . æ 1 ö æ 1 ö 5 p0 = Fç x0 + 1, y0 - ÷ = Fç1, R - ÷ = - R è 2 ø è 2 ø 4 Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 17/22
33. ÑOÀ HOÏA MAÙY TÍNH 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); x<y No Yes p<0 No Yes p=p+2*x+3; p=p+2(x-y)+5; y=y-1 x=x+1; Put8Pixel(x,y,c); End Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 18/22
34. ÑOÀ HOÏA MAÙY TÍNH Caøi ñaët minh hoïa thuaät toaùn MidPoint veõ ñöôøng troøn void CircleMidPoint (int R) { int x, y; x = 0; y = R; Put8Pixel(x, y); p = 1 - R; // 5/4-R while (x < y) { if (p < 0) p += 2*x + 3; else { p += 2*(x -y) + 5; y ; } x++; Put8Pixel(x, y); } } // CircleMidPoint Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 19/22
35. ÑOÀ HOÏA MAÙY TÍNH · Ví duï : Veõ ñöôøng troøn taâm I(0,0), baùn kính R=15. ii xii yI pii Dellta1 Dellta2 0 0 15 -14 1-15 3 -25 1 1 15 -11 -14+2*(0)+3 5 -23 2 2 15 -6 -11+2*(1)+3 7 -21 3 3 15 1 -6+2*(2)+3 9 -19 4 4 14 -18 1+2*(3-15)+5 11 -15 5 5 14 -7 -18+2*(4)+3 13 -13 6 6 14 6 -7+2*(5)+3 15 -11 7 7 13 -5 6+2(6-14)+5 17 -7 8 8 13 12 -5+2(7)+3 19 -5 9 9 12 7 12+2(8-13)+5 21 -1 10 10 11 6 7+2(9-12)+5 23 3 11 11 10 9 6+2(10-11)+5 25 7 Nhaän xeùt : · Neáu ñaët Delta1 = 2*x+3, Delta2 = 2*(x-y)+5 thì ¨ Do moãi böôùc ñeàu taêng x neân sau moãi laàn laëp giaù trò Delta1 luoân taêng 2. ¨ Do y bò giaûm 1 khi gaëp p³0 vaø giöõ nguyeân giaù trò trong tröôøng hôïp ngöôïc laïi neân neáu laàn laëp tröôùc giaù trò p³0 thì giaù trò Delta2 seõ ñöôïc taêng 4 vaø neáu laàn laëp tröôùc giaù trò p<0 thì giaù trò Delta2 seõ ñöôïc taêng 2 maø thoâi. · Haõy toái öu hoùa caøi ñaët thuaät toaùn MidPoint veõ ñöôøng troøn töø nhaän xeùt treân. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 20/22