Luận văn Thiết kế hệ thống kiểm tra các quan hệ hình học trong 2D và 3D
Tài liệu Luận văn Thiết kế hệ thống kiểm tra các quan hệ hình học trong 2D và 3D: Trong lĩnh vực công nghệ máy tính cũng như công nghệ thông tin có những bước phát triển nhảy vọt, nó đã hỗ trợ vào mọi lĩnh vực trong cuộc sống xã hội, sản phẩm của công nghệ thông tin biến đổi hàng ngày, hàng giờ. Trong lĩnh vực toán học, các sản phẩm của công nghệ thông tin cũng hỗ trợ đắc lực cho việc học tập và nghiên cứu. Đề tài tôi thực hiện là: “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC TRONG KHÔNG GIAN 2D VÀ 3D“. Đề tài sử dụng ngôn ngữ lập trình Visual C++ để thể hiện. Về góc độ học tập, nghiên cứu tôi thấy đề tài có thể giúp hiểu rõ thêm về kiến thức cơ bản của phần đồ họa máy tính và cho vấn đề kiểm tra thực hiện một số bài toán hình học thêm phong phú hơn, tạo thêm phần hấp dẫn trong môn học này. Trong thời gian thực hiện đề tài tôi đã thực hiện được những yêu cầu của đề tài. Việc thực hiện đề tài còn mang ý nghĩa...
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Thiết kế hệ thống kiểm tra các quan hệ hình học trong 2D và 3D, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Trong lónh vöïc coâng ngheä maùy tính cuõng nhö coâng ngheä thoâng tin coù nhöõng böôùc phaùt trieån nhaûy voït, noù ñaõ hoã trôï vaøo moïi lónh vöïc trong cuoäc soáng xaõ hoäi, saûn phaåm cuûa coâng ngheä thoâng tin bieán ñoåi haøng ngaøy, haøng giôø. Trong lónh vöïc toaùn hoïc, caùc saûn phaåm cuûa coâng ngheä thoâng tin cuõng hoã trôï ñaéc löïc cho vieäc hoïc taäp vaø nghieân cöùu.
Ñeà taøi toâi thöïc hieän laø: “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC TRONG KHOÂNG GIAN 2D VAØ 3D“. Ñeà taøi söû duïng ngoân ngöõ laäp trình Visual C++ ñeå theå hieän. Veà goùc ñoä hoïc taäp, nghieân cöùu toâi thaáy ñeà taøi coù theå giuùp hieåu roõ theâm veà kieán thöùc cô baûn cuûa phaàn ñoà hoïa maùy tính vaø cho vaán ñeà kieåm tra thöïc hieän moät soá baøi toaùn hình hoïc theâm phong phuù hôn, taïo theâm phaàn haáp daãn trong moân hoïc naøy. Trong thôøi gian thöïc hieän ñeà taøi toâi ñaõ thöïc hieän ñöôïc nhöõng yeâu caàu cuûa ñeà taøi.
Vieäc thöïc hieän ñeà taøi coøn mang yù nghóa ñaùnh giaù laïi quaù trình hoïc taäp, nghieân cöùu cuûa toâi. Neân veà maët tinh thaàn toâi ñaõ coá gaéng tìm hieåu, nghieân cöùu, vaø chuaån bò khaù chu ñaùo cho vieäc thöïc hieän. Nhöng söï tieáp thu cuõng coù nhöõng giôùi haïn nhaát ñònh, bôûi trong lónh vöïc maùy tính cuõng nhö cô sôû toaùn hoïc roäng lôùn, khoâng gian dieãn dòch coù theå voâ haïn, söï thöïc hieän moät yù töôûng naøo ñoù coù theå trong toaùn hoïc thöïc hieän ñöôïc, nhöng vieäc theå hieän thuaät toaùn baèng maùy tính thì coù nhöõng vaán ñeà khoù theå thöïc hieän, vì vaäy ñeà taøi chaéc chaén coøn nhieàu thieáu soùt nhaát ñònh.
Mong quyù Thaày coâ, Anh chò vaø caùc baïn thoâng caûm, ñoùng goùp yù kieán giuùp ñôõ. Toâi thaønh thaät caûm ôn …!
SINH VIEÂN THÖÏC HIEÄN
LEÂ QUOÁC THAÙI
PHAÀN I: GIÔÙI THIEÄU
SÔ LÖÔÏC VEÀ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC
Ñeå cho ngöôøi ñoïc tham khaûo ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“ deã daøng hình dung ñöôïc, toâi xin giôùi thieäu sô löôïc veà ñeà taøi.
Nhieäm vuï thöïc hieän cuûa ñeà taøi:
Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trong:
Khoâng gian hai chieàu (2D)
Khoâng gian ba chieàu (3D)
Vôùi ngoân ngöõ theå hieän treân moâi tröôøng Visual C++.
Ñeà taøi aùp duïng caùc kieán thöùc veà cô sôû toaùn hoïc vaø khoâng gian vector trong ñoà hoïa maùy tính, ñeå xaây döïng nhöõng thuaät toaùn kieåm tra caùc quan heä hình hoïc.
Ñeå deã daøng hôn toâi xin trình baøy moät ví duï ñieån hình nhö sau:
Ví duï: cho ñöôøng thaúng a qua hai ñieåm A vaø B vaø ñöôøng thaúng b qua hai ñieåm C vaø D trong khoâng gian 2D hay 3D thì hai ñöôøng thaúng naøy cuõng coù nhöõng söï töông quan vôùi nhau, nhö truøng nhau, caét nhau vôùi moät goùc naøo ñoù, cheùo nhau (trong khoâng gian 3D), hay song song… Sau khi ñöa vaøo nhöõng ñieàu kieän giaû thieát ban ñaàu (Input), thì chöông trình thöïc hieän vaø ñöa ra keát quaû kieåm tra (output) cuûa giaû thieát treân laø hai ñöôøng thaúng a vaø b ñaõ töông quan nhö theá naøo vôùi nhau? Caét nhau moät goùc bao nhieâu ñoä, song song, hay truøng nhau...
Ñoù laø veà maët thuaät toaùn chöông trình kieåm tra, ñaây chæ môùi laø moät taùc vuï thöïc hieän cuûa vaán ñeà naøy. Vôùi baøi toaùn nhö treân neáu chæ ñöa ra ñöôïc nhöõng keát luaän vôùi nhöõng doøng thoâng ñieäp thì chuùng ta thaáy raèng ñeà taøi trôû neân quaù ñôn giaûn khoâng phong phuù vaø haáp daãn qua yù kieán cuûa ngöôøi ñoïc hoaëc tham khaûo. Moät taùc vuï cuøng ñoàng thôøi vôùi baøi toaùn treân maø nhieäm vuï cuûa ñeà taøi yeâu caàu thöïc hieän laø khi ñöa vaøo giaû thieát baøi toaùn chaúng haïn hai ñieåm A vaø B vôùi nhöõng toïa ñoä xaùc ñònh naøo ñoù, qua hai ñieåm naøy seõ thöïc hieän veõ leân moät ñoaïn thaúng qua hai ñieåm A vaø B. Töø ñoù thaáy vaán ñeà moät caùch tröïc quan hôn, hay veõ ra goùc giöõa hai ñöôøng thaúng, chính vôùi nhöõng theå hieän naøy ñeà taøi trôû neân haáp daãn phong phuù hôn, taát nhieân vaán ñeà naøy khoâng ít nhöõng khoù khaên cho ngöôøi thöïc hieän ñeà taøi.
Trong phaàn noäi dung toâi seõ trình baøy chi tieát hôn veà ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC TRONG 2D VAØ 3D“.
GIÔÙI THIEÄU SÔ LÖÔÏC NGOÂN NGÖÕ THEÅ HIEÄN ÑEÀ TAØI
1. SÔ LÖÔÏC NGOÂN NGÖÕ
ÔÛ phaàn I giôùi thieäu sô löôïc veà “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“, toâi ñaõ trình baøy moät ví duï veà yeâu caàu nhieäm vuï ñeå thöïc hieän moät taùc vuï kieåm tra vaán ñeà naøo ñoù cuûa ñeà taøi naøy. Ñeå thöïc hieän nhöõng vaán ñeà ñoù toâi nghieân cöùu vaø thöïc hieän treân moâi tröôøng ngoân ngöõ Visual C++.
Visual C++ laø moät phaàn meàm laäp trình höôùng ñoái töôïng ñöôïc phaùt trieån treân cô sôû laø ngoân ngöõ laäp trình C vaø C++. ÔÛ ñaây toâi theå hieän ñeà taøi treân ngoân ngöõ Visual C++ bôûi leõ hieän nay ngoân ngöõ naøy ñöôïc xem laø moät trong caùc ngoân ngöõ hoã trôï (support user) maïnh vaø phoå bieán nhaát. Cuøng muïc ñích saâu xa hôn nöõa laø ñeå cho nhöõng ñeà taøi sau naøy coù theå treân cuøng ngoân ngöõ xaây döïng yù töôûng cuûa ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“ ngaøy theâm moät ñaày ñuû, phong phuù, haáp daãn vaø öùng duïng mang tính thieát thöïc hôn. Toâi ñaàu tieân nghieân cöùu tìm hieåu toång quaùt veà ngoân ngöõ nhö Visual C++, thöïc hieän nhöõng chöông trình ñieån hình treân ngoân ngöõ laäp trình höôùng ñoái töôïng. Vaø phaàn tìm hieåu chính laø phaàn thöïc hieän yeâu caàu cuûa ñeà taøi, cuï theå laø veà phöông dieän tính toaùn trong nhöõng thuaät toaùn vaø theå hieän tröïc quan baèng ñoà hoaï maùy tính treân ngoân ngöõ Visual C++.
Trong Visual C++ phaàn ñoà hoïa ñöôïc theå hieän trong lôùp CDC (Class Device Context) vôùi nhieàu haøm thaønh vieân hoã trôï cho vieäc veõ ñieåm, ñöôøng, ña giaùc, toâ maøu…. Ñaëc bieät hôn trong ngoân ngöõ Visual C++ coù söï hoã trôï cho vieäc veõ caùc ñoái töôïng hình hoïc baèng chuoät. Nhöng ngoân ngöõ chæ thöïc hieän ñöôïc vôùi caùc ñoái töôïng hình hoïc 2D, ñoái töôïng hình hoïc 3D thì chöa coù, caàn phaûi töï thieát keá.
Trong quaù trình nghieân cöùu, toâi nhaän thaáy trong ngoân ngöõ Visual C++ coù boä thö vieän OPENGL laø moät thö vieän API hoã trôï cho vieäc thöïc hieän caùc chöông trình ñoà hoïa, treân caû 2D vaø 3D raát maïnh, chính vì theá ôû phaàn kieåm tra caùc quan heä hình hoïc phaàn 3D toâi thöïc hieän treân OPENGL. Töø ñaây toâi chuyeån höôùng sang nghieân cöùu OPENGL ñeå thöïc hieän cho phaàn 3D. Ñeå hieåu vaø thöïc hieän ñöôïc treân noù cuõng khoù khaên khoâng keùm nhö ta baét ñaàu nghieân cöùu vaø laøm quen vôùi ngoân ngöõ môùi nhö Visual C++. Sau khi nghieân cöùu vaø hieåu ñöôïc nhöõng yeáâu toá cô baûn cuûa OPENGL toâi coù nhaän xeùt raèng OPENGL laø moät öùng duïng ñeå thöïc hieän caùc chöông trình ñoà hoïa maùy tính haáp daãn vaø ñeïp maét. Khi ñaõ caøi ñöôïc thì caùch söû duïng coù phaàn deã daøng hôn, chæ caàn tìm hieåu moät soá caùc haøm trong thö vieän caùc haøm thaønh vieân cuûa OPENGL laø ñaùp öùng ñöôïc yeâu caàu. Coøn moïi vieäc thöïc hieän caøi ñaët theo lyù thuyeát ñoà hoïa maùy tính nhö caùc pheùp bieán hình, thieát laäp cheá ñoä maøn hình, khôûi taïo ñoà hoïa, setviewport, taïo caùc Pallette maøu, thieát laäp ñoä saâu hình aûnh, ñoä phaûn chieáu hình aûnh, ñoä töông phaûn … taát caû do OPENGL hoã trôï haàu heát.
OpenGL ñöôïc ñònh nghóa laø “giao dieän phaàn meàm cho phaàn cöùng ñoà hoïa ”. Thöïc chaát, OpenGL laø moät thö vieän caùc haøm ñoà hoïa, ñöôïc xem laø tieâu chuaån thieát keá coâng nghieäp cho ñoà hoïa ba chieàu.
Vôùi giao dieän laäp trình maïnh meõ, OpenGL cho pheùp taïo caùc öùng duïng 3-D phöùc taïp vôùi ñoää tinh vi, chính xaùc cao, maø ngöôøi thieát keá khoâng phaûi ñaùnh vaät vôùi caùc nuùi coâng thöùc toaùn hoïc vaø caùc maõ nguoàn phöùc taïp. Vaø do OpenGL laø tieâu chuaån coâng nghieäp, caùc öùng duïng taïo töø noù duøng ñöôïc treân caùc phaàn cöùng vaø heä ñieàu haønh khaùc nhau.
Nhaän xeùt veà OPENGL toâi thaáy raèng OPENGL laø thö vieän ñoà hoïa treân WINDOWS bôûi vì ta coù theå thaáy raèng OPENGL khoâng nhöõng thöïc hieän treân ngoân ngöõ Visual C++ maø coøn coù theå cho pheùp thöïc hieän treân caû Visual Basis , Borland C++
2. GIÔÙI THIEÄU CAÙC HAØM CUÛA NGOÂN NGÖÕ ÑÖÔÏC SÖÛ DUÏNG
a. Caùc haøm cuûa lôùp CDC (Class Device Context)
Trong CDC coù raát nhieàu haøm thaønh vieân phuïc vuï cho quaù trình keát xuaát caùc hình aûnh ra caùc thieát bò. Trong phaàn thöïc hieän ñeà taøi, toâi xin ñöa ra caùc haøm ñöôïc söû duïng trong ñeà taøi
Veõ ñieåm:
SetPixel ( int x , int y , int color );
Haøm naøy thuoäc lôùp CClientDC trong phaàn maøu söû duïng macro RGB(red,green,blue)
Ví du:ï Ñeå veõ moät ñieåm , ta thöïc hieän nhö sau:
CClientDC dc( this );
dc.SetPixel (100,100,GRB(0,0,0);
Ñeå theå hieän toïa ñoä moät ñieåm trong heä truïc toïa ñoä hai chieàu, Visual C++ duøng lôùp CPoint, ñoái töôïng thuoäc lôùp naøy ñöôïc theå hieän bôûi hai thaønh phaàn x vaø y. Ví duï ta khai baùo ñieåm point nhö sau:
CPoint point
point.x=100;
point.y=100;
Veõ ñöôøng thaúng:
Line (int x1, int y1, int x2, int y2);
Haøm naøy thuoäc lôùp CClientDC
Ví duï: Ñeå veõ ñöôøng thaúng ta thöïc hieän caùc böôùc sau ñaây
CClientDC dc(this);
dc.Line(x1,y1,x2,y2);
Ngoaøi ra trong vieäc veõ ñöôøng thaúng coøn coù theå söû duïng hai haøm sau:
MoveTo(int x, int y);
Haøm naøy duøng ñeå di chuyeån con troû ñeán toïa ñoä x,y trong maøn hình.
LineTo(int x, int y);
Haøm naøy duøng ñeå veõ ñöôøng thaúng töø ñieåm hieän haønh ñeán ñieåm x, y.
Caû hai haøm naøy ñeàu thuoäc lôùp CClientDC, vieäc söû duïng nhö sau:
CClientDC dc(this);
dc.MoveTo(x,y);
dc.LineTo(newx, newy);
Veõ hình chöõ nhaät:
Rectangle(int x1,int y1,int x2,int y2);
Haøm naøy thuoäc lôùp CclientDC. Duøng ñeå veõ hình chöõ nhaät coù toïa ñoä treân goùc treân traùi laø (x1,y1) vaø toïa ñoä goùc döôùi phaûi laø (x2,y2). Cuù phaùp veõ hình chöõ nhaät nhö sau:
CClientDC dc(this);
dc.Rectangle(x1, y1, x2, y2);
Veõ hình Ellipse:
Ellipse(int x1,int y1,intx2,int y2);
Haøm naøy coù caùc tham töông töï caùc tham soá hình chöõ nhaät, haøm naøy cuõng thuoäc lôùp CClientDC. Cuù phaùp veõ hình Ellipse nhö sau:
CClientDC dc(this);
dc.ellipse(int x1, int y1, intx2, int y2);
Haøm loan vuøng kín:
FloodFill(int x,int y, int color);
Haøm naøy duøng ñeå toâ maøu vuøng ñöôïc giôùi haïn bôûi moät ñöôøng bieân kheùp kín. Haøm naøy thuoäc lôùp CClientDC coù taùc duïng toâ maøu vôùi maøu color toâ heát vuøng coù toïa ñoä (x,y) vaø moät vuøng kín bao quanh ñieåm ñoù. Cuù phaùp haøm nhö sau:
CClientDC dc(this);
dc.FloodFill(x, y, color);
Taïo caùc ñöôøng veõ:
CreatePen(typeline, width, color);
Ñeå taïo ñöôøng veõ trong caùc öùng duïng veõ ta xeùt haøm CreatePen cuûa lôùp Cpen, haøm naøy coù daïng nhö sau:
Cpen *pPen=new Cpen;
pPen->CreatePen(typeline, width, color);
Trong ñoù :
· Tham soá typeline laø kieåu ñöôøng veõ, noù coù giaù trò ñöôïc ñònh nghóa nhö sau:
PS-SOLID Ñöôøng thaúng ñoàng nhaát.
PS-DASH Ñöôøng thaúng goàm caùc gaïch ngang ñöùt neùt.
PS-DOT Ñöôøng thaúng goàm caùc neùt chaám ñöùt.
PS-DASDOT Ñöôøng thaúng goàm caùc gaïch ngang chaám ñöùt.
PS-DASHDOTDOT Ñöôøng thaúng goàm caùc gaïch ngang chaám ñöùt.
PS-NULL Ñöôøng thaúng voâ hieäu löïc khoâng veõ ra.
PS-INSIDEFRAME Ñöôøng thaúng naèm beân trong ñöôøng vieàn.
· Tham soá width cho ñoä roäng cuûa neùt veõ tính baèng pixel.
· Tham soá color cho maøu veõ
b. Caùc haøm trong boä thö vieän OpenGL
OpenGL goàm 5 boä haøm, boä haït nhaân coù 115 haøm cô baûn. Teân caùc haøm naøy baét ñaàu baèng GL. Windows NT hoã trôï 4 chuûng loaïi haøm khaùc, bao goàm thö vieän OpenGL utility(teân haøm baét ñaàu baèng GLU), thö vieän OpenGL auxiliary(teân haøm baét ñaàu baèng AUX), boä haøm”WGL” (teân haøm baét ñaàu baèng WGL), vaø caùc haøm WIN32 API (teân haøm khoâng coù tieàn toá ñaëc bieät). Boä haøm haït nhaân cho pheùp thieát keá caùc hình daïng khaùc nhau, taïo caùc hieäu quaû chieáu saùng, keát hôïp antialiasing vaø gaùn caáu truùc, thöïc hieän bieán ñoåi ma traän…
Do caùc haøm cô baûn ñöôïc theå hieän ôû nhieàu daïng khaùc nhau tuøy thuoäc vaøo loaïi döõ lieäu maø chuùng tieáp nhaän, neân treân thöïc teá coù hôn 300 nguyeân maãu (prototype) caùc haøm cô baûn.
ó Thö vieän OpenGL utility goàm caùc haøm cao caáp. Caùc haøm naøy ñôn giaûn hoaù vieäc söû duïng hình aûnh caáu truùc, thöïc hieän vieäc bieán ñoåi toïa ñoä möùc cao, hoã trôï tesselation ña giaùc, vaø bieåu dieãn caùc ñoái töôïng coù cô sôû ña giaùc nhö hình caàu, hình truï hình dóa.
ó Thö vieän OpenGl auxiliary goàm caùc haøm ñaëc bieät duøng ñôn giaûn hoùa caùc ví duï laäp trình trong saùch chæ daãn laäp trình OpenGL. Caùc haøm phuï thuoäc platform naøy thöïc hieän caùc nhieäm vuï nhö quaûn kyù cöûa soå, ñieàu khieån xuaát/nhaäp, veõ caùc ñoái töôïng 3D nhaát ñònh. Do caùc haøm naøy coù möïc ñích thieát minh neân khoâng ñöôïc duøng trong caùc maõ saûn xuaát.
ó Caùc haøm “WGL”keát noái OpenGL vôùi WINdows NT, cho pheùp ngöôøi laäp trình xaây döïng vaø choïn löïa caùc ngöõ caûnh bieåu dieãn, taïo caùc bitmap font, caùc haøm naøy chæ duøng treân Windows NT.
ó Cuoái cuøng, caùc haøm Win32 API ñöôïc duøng giaûi quyeát caùc ñònh daïng ñieåm aûnh vaø taïo boä ñeäm ñoâi.
Trong phaàn naøy, toâi trình baøy moät soá haøm ñöôïc söû duïng trong ñeà taøi.
Haøm veõ ñieåm, ñöôøng, ña giaùc:
Ñöôïc baét ñaàu bôûi haøm:
glBegin (Glenum mode)
Ñeå chæ söï baét ñaàu nhöõng ñænh cuûa moät primitive, tham soá mode chæ kieåu caùc primitive.
Tham soá mode coù caùc giaù trò sau:
GL_POINTS : chæ ñænh ñöôïc söû duïng laø ñieåm.
GL_LINES : chæ nhöõng ñænh ñöôïc duøng ñeå taïo ñoaïn thaúng.
GL_LINE_STRIP : chæ nhöõng ñænh ñöôïc söû duïng taïo ñoaïn thaúng nhaün.
GL_TRIANGLES : nhöõng ñænh ñöôïc söû duïng taïo ra nhöõng tam giaùc.
GL_TRIANGLE_STRIP : nhöõng ñænh ñöôïc söû duïng taïo ra tam giaùc coù caïnh nhaün.
GL_POLYGON : nhöõng ñænh ñöôïc söû duïng taïo ra ña giaùc loài.
glEnd ( )
Haøm treân duøng ñeå chaám döùt danh saùch caùc ñænh maø noù chæ roõ primitive ñöôïc khôûi taïo bôûi haøm glBegin.
Ví du: Veõ ñöôøng thaúng töø 2 ñieåm
glBegin(GL_LINES)
glVertex3f(0.0f, 0.0f, 0.0f);
glVertex3f(50.0f, 50.0f, 50.0f);
glEnd( );
Haøm chæ ra toïa ñoä cuûa ñieåm, ñöôøng, ña giaùc:
glVertex2f (Glfloat x,Glfloat y)
glVertex3f (Glfloat x,Glfloat y,Glfloat z)
Haøm bieán ñoåi toïa ñoä:
· glLoadIdentity(); thay theá ma traän hieän haønh bôûi ma traän ñôn vò.
· glMultMatrix(); nhaân ma traän hieän haønh vôùi ma traän ñöôïc chæ ñònh.
· gl PopMatrix(void); laáy ma traän hieän haønh töø stack.
· glPushMatrix(void); ñaåy ma traän hieän haønh vaøo stack.
· glTranslatef (Glfloat x, Glfloat y, Glfloat z); nhaân ma traän hieän haønh bôûi ma traän tònh tieán.
· gl Rotatef(Glfloat Angle, Glfloat x, Glfloat y, Glfloat z); nhaân ma traän hieän haønh bôûi ma traän quay.
Caùc haøm lieân quan ñeán maøu:
· glColor3f (Glfloat red, Glfloat green, Glfloat blue); ñaët maøu hieän haønh bôûi caùc thaønh phaàn red, green, blue vôùi giaù trò töø 0,0 ñeán 1,0.
· glClearColor(GLclampf red, GLclamp green, Glclamp blue, Glclamp alpha); ñaët maøu cho vieäc xoùa buffer maøu.
· glClear(GL_COLOR_BUFFER_BIT); xoùa buffer maøu, xoùa cöûa soå bôûi maøu xoùa hieän haønh .
Caùc haøm lieân quan ñeán aùnh saùng:
· glLightf(Glenum light, Glenum pname, GLfloat param);
· glLighti(Glenum light, Glenum pname, GLint param);
Trong ñoù:
E Tham soá light chæ ra nguoàn saùng coù giaù trò töø GL_LIGHT0 ñeán GL_LIGHT7.
E Tham soá pname chæ ra tham soá light naøo ñöôïc laäp nhö GL_AMBIENT, GL_DIFFUSE…
E Tham soá param chæ coù yù nghóa ñoái vôùi nguoàn saùng ñieåm. Tham soá naøy coù caùc giaù trò nhö: GL_SPOT_EXPONENT, GL_SPOT_CUTOFF…
Caùc haøm lieân quan ñeán thuoäc tính aùnh saùng cuûa vaät lieäu:
· glColorMaterialf(Glenum face,Glenum pname, GL float param);
· glMateriali(Glenum face,Glenum pname, GL int param);
· glMaterialfi(Glenum face,Glenum pname, const Glint* params);
· glMaterialfi(Glenum face,Glenum pname, const Glint* params);
Trong ñoù:
E face: laø thuoäc tính beà maët tröôùc ,sau cuûa ña giaùc.
E pname: laø thuoäc tính cuûa vaät lieäu: GL_AMBIENT,GL_DIFFUSE,…
E param : chæ ñònh giaù trò maø tham soá pname ñöôïc laäp.
E params: chæ ñònh daõy soá nguyeân hay thöïc chöùa caùc thaønh phaàn thuoäc tính ñöôïc laäp.
· glFrontFace(Glenum mode); xaùc ñònh beà maët ña giaùc laø maët tröôùc hay sau.
PHAÀN II: NOÄI DUNG
Trong phaàn giôùi thieäu toâi ñaõ trình baøy nhöõng noäi dung sô löôïc mang tính toång quaùt cuûa ñeà taøi. Phaàn noäi dung toâi trình baøy chi tieát hôn theo thöù töï logic caùc vaán ñeà töø lyù thuyeát toaùn hoïc ñeán caùc thuaät toaùn chöông trình.
I. LYÙ THUYEÁT CÔ SÔÛ TOAÙN HOÏC
Caùc lyù thuyeát cô sôû toaùn hoïc ñöôïc söû duïng cho caùc thuaät toaùn trong ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“ bao goàm:
· Hình hoïc giaûi tích trong maët phaúng
· Hình hoïc giaûi tích trong khoâng gian.
Phaàn lyù thuyeát cô sôû toaùn hoïc naøy raát caàn thieát cho vieäc thieát keá chöông trình thöïc hieän vieäc kieåm tra caùc quan heä hình hoïc, khoâng gian vector laø cô sôû lyù thuyeát toaùn hoïc taát yeáu ñeå xaây döïng caùc caáu truùc ñoà hoïa maùy tính.
I.1. Giôùi thieäu veà vector:
Ñieåm (point): Moâ taû caùc vò trí cuûa ñoà hình vaø coù nhieàu caùch ñeå dieãn ñaït. Trong hai chieàu bieåu dieãn baèng caùch duøng boä-2 ñeå cho caùc toïa ñoä theo hai truïc. Hai daïng thöôøng ñöôïc aùp duïng nhieàu ñoù laø daïng Cartesian nhö (x,y) =(3,4) hay daïng toïa ñoä cöïc (R, q)=(2.4,450).
Trong khi chuùng ñöôïc ñònh nghóa moät caùch ñaïi soá theo caùc thao taùc nhaát ñònh treân ñoù, chuùng cuõng cho pheùp moät dieãn dòch hình hoïc theo caùc ñieåm, ñöôøng, chieàu.
Vector: Nhìn moät caùch hình hoïc, vector laø moät ñoaïn thaúng maø caùc ñieåm ñaàu vaø ñieåm cuoái ñaõ ñöôïc xaùc ñònh . Vector laø moät ñoái töôïng coù ñoä daøi vaø chieàu töông öùng vôùi moät soá thöïc theå vaät lyù nhö löïc, khoaûng caùch, vaø vaän toác. Vector thöôøng ñöôïc veõ nhö moät muõi teân coù chieàu daøi chæ veà moät höôùng.
Khi vector ñöôïc choïn ñeå chæ ñònh heä toïa ñoä, caùc vector coù moät haøm soá ñeå ñöa ra hai haèng soá, ba haèng soá,... Vì theá, moät trong caùc theå hieän cuûa moät vector hai chieàu a laø moät caëp coù thöù töïï a=(a, a). Trong chöông trình, vector ñöôïc bieåu dieãn baèng kieåu döõ lieäu:
Typedef struct
{
dx,dy: float;
} vector;
struct
{
dx,dy,dz : float;
} vector3D
x
P2
v
P4
P3
v
P1
y
P5
Vôùi hai ñieåm P1(x1,y1) vaø P2(x2,y2) ta ñònh nghóa vector v vôùi caùc thaønh phaàn laø vector v =(x2-x1, y2-y1). Ñoâi khi vector naøy ñöôïc ghi laø P1P2 vaø goïi laø vector töø P1 ñeán P2. Baûn thaân vector khoâng bò buoäc vaøo moät vò trí, maëc duø ñeå deã hình dung thöôøng veõ chuùng xuaát phaùt töø moät ñieåm. Vôùi ñieåm baát kyø P = (Px, Py) trong moät heä toïa ñoä, vector ñi töø goác toïa ñoä vôùi caùc toïa ñoä v=(Px, Py) ñöôïc goïi laø vector vò trí cho P. Vector 3D cuõng raát quan troïng trong ñoà hoïa.
I.2. Caùc pheùp tính vector:
Moät vector n chieàu, vôùi n laø soá nguyeân döông baát kyø:
W=(W1,W2,. . .,Wn)
vôùi moãi thaønh phaàn Wi laø soá voâ höôùng.
Caùc vector 2 chieàu vaø 3 chieàu vôùi n=2, n=3 thì thöôøng gaëp nhaát trong ñoà hoaï Chuùng ta khoâng theå thaáy ñöôïc caùc vector lôùn hôn 3 nhöng chuùng laø nhöõng thaønh phaàn coù giaù
rò raât lôùn.
Hai pheùp tính soá hoïc cô baûn treân vector laø coäng hai vector vaø ñònh tyû leä moät vector.
Coäng hai vector
Toång hai vector a,b laø vector c ñöôïc ñònh nghóa nhö sau:
C = (c, c, …, c) = (a + b, a + b, …, a + b)
b
a+b
a
a+b
b
a
Hình b
Hình a
Hình a: Caùc thaønh phaàn cuûa toång laø toång caùc thaønh phaàn cuûa caùc vector tham gia.
Hình b: Toång caùc vector laø ñöôøng cheùo hình bình haønh.
Procedure AddVectors( vector a, vector b; vector &c );
{
c.dx := a.dx + b.dx;
c.dy := a.dy + b.dy;
}
Ñònh tyû leä moät vector
Vieäc ñònh tyû leä moät vector nhaèm thay ñoåi ñoä daøi cuûa hay ñaûo chieàu cuûa noù.
sa = (sa, sa, …, sa)
Vôùi s laø heä soá tyû leä vaø a laø vector. Khi s aâm, chieàu cuûa sa ngöôïc laïi vôùi a.
Procedure Scalar(real s; vector a; vector &b)
{
b.d = sa.d ;
b.d= sa.d;
}
Pheùp tröø hai vector:
Treân cô sôû coäng vaø ñònh tyû leä, pheùp tröø deã daøng ñònh nghóa:
a-c = a +(-c)
vôùi thaønh phaàn thöù i laø ai-ci.
a
a-c
c
-c
Trò tuyeät ñoái (ñoä daøi) cuûa vector
Neáu moät vector W ñöôïc theå hieän trong khoâng gian nhieàu chieàu (W, W, …, W), döïa theo ñònh lyù Pithagore ta coù coâng thöùc sau:
Vector coù ñoä daøi baèng zero thöôøng ñöôïc goïi laø vector 0. Chöông trình con minh hoïa nhö sau: Function Length(vector v): Real;
· Chuaån hoùa vector -Vector ñôn vò
Vieäc ñònh tyû leä moät vector ñeå keát quûa coù ñoä daøi baèng 1 goïi laø chuaån hoaù moät vector, vaø keát quûa goïi laø vector ñôn vò. Ví duï daïng chuaån hoaù ua cuûa a nhö sau:
ua = a / | a|
vaø coù cuøng chieàu vôùi a.
Bieåu thöùc cho heä soá cuûa vector coù theå khai baùo tröïc tieáp nhö sau:
Normalize(vector v, vector &u);
Noù coù daïng vector ñôn vò u do caùc heä soá moãi thaønh phaàn cuûa v:
u.d:= v.d/Length(v);
u.d:= v.d/Length(v);
Toå hôïp tuyeán tính cuûa vector:
Ñeå hình thaønh toå hôïp tuyeán tính cuûa hai vector V vaø W, ñònh tyû leä moãi vector theo caùc tyû soá a vaø b roài coäng keát quûa ñeå thaønh vector môùi av+bw.
Toång quaùt, toå hôïp tuyeán tính cuûa m vector V, V, …, V nhö sau:
W = aV + aV + …+ aV
Procedure Combo2D(float a,b vector u,v ,vector &W );
{
w.dx:=a*u.dx+b*v.dx;
w.dy:=a*u.dy+b*v.dy;
}
· Toå hôïp loài cuûa vector
Moät lôùp ñaëc bieät cuûa toå hôïp tuyeán tính coù vò trí quan troïng trong toaùn hoïc vaø öùng duïng soá hoïc trong ñoà hoïa, ñoù laø:Toå hôïp loài (convex combination), hay toå hôïp tuyeán tính maø caùc heä soá khoâng aâm vaø toång baèng 1. Vaäy toå hôïp tuyeán tính:
W = aV + aV + … +aV
laø toå hôïp loài neáu toång =1vaø a0, vaø cung “spline” thöïc ra laø toå hôïp loài cuûa moät taäp caùc vector.
Tích voâ höôùng cuûa hai vector:
Tích voâ höôùng cuûa hai vector cho ta thoâng tin ñaùng giaù veà moät caëp vector nhö goùc giöõa chuùng (cuï theå laø khi naøo chuùng vuoâng goùc) vaø chieáu vector leân vector khaùc. Noù cuõng cho ta phöông trình cuûa moät maët phaúng moâ taû baèng moät ñieåm vaø hai vector.
Cho hai vector, ví duï hai chieàu (a1,a2) vaø (b1,b2).
Tích voâ höôùng hai vector ñònh nghóa laø:
a.b = a1b1+ a2b2
Moät caùch toång quaùt cho vector n chieàu nhö sau: Cho Vector V= (v, v, …, v) vaø W=( w, w, …, w), tích voâ höôùng cuûahai vector treân laø:
V. W = vôùi i = 1,… ,n
Tích voâ höôùng cuûa hai vector ñöôïc theå hieän trong thuû tuïc sau:
Procedure Float Dot (vector a,b)
{
return Dot = a.d* b.d+ a.d* b.d;
}
· Caùc tính chaát cuûa tích voâ höôùng
1. Ñoái xöùng : a.b = b.a
2. Tuyeán tính: (a+c).b = a.b + c.b
3. Ñoàng nhaát : (sa).b = s(a.b)
4. | b2 | = b.b
Ñoä daøi cuûa hieäu vaø toång hai vector ñöôïc cho nhö sau:
| a-b|2 = |a|2 - 2ab + |b|2
| a+b|2 = |a|2 + 2ab + |b|2
Caùc öùng duïng cuûa tích voâ höôùng:
Goùc giöõa hai vector (hay hai ñöôøng)
Ñaây laø öùng duïng quan troïng cuûa tích voâ höôùng. Hình a döôùi cho thaáy goùc q giöõa hai vector a vaø b. Caùc vector naøy coù theå coù hai, ba, hay nhieàu chieàu. Chuùng taïo thaønh hai caïnh cuûa tam giaùc, vaø caïnh thöù ba laø a-b. Theo heä thöùc löôïng trong tam giaùc, ta coù :
| a-b|2 = |a|2 + |b|2 - 2 |a||b|cos(q)
Töø phöông trình naøy vaø phöông trình
| a-b|2 = |a|2 - 2ab + |b|2
ta suy ra ñöôïc: a.b = |a||b| cos(q)
Nghóa laø cos(q) = ua.ub
a
b
Hình a
Vaäy cosin cuûa goùc giöõa hai vector a vaø b laø tích voâ höôùng cuûa daïng chuaån hoùa hai vector.
* Daáu cuaû vector a.b vaø söï tröïc giao
Ta bieát raèng
cos() >0 neáu < 90
cos() 90
cos() =0 neáu = 0
Do vaäy töø phöông trình:
cos() = u.u
ta coù goùc giöõa hai vector nhö sau:
l Nhoû hôn 90o neáu a.b >0
l Baèng 900 neáu a.b = 0
l Lôùn hôn 90o neáu a.b < 0
a.b>0
a.b=0
a.b<0
a
a
a
b
b
b
Chieáu vaø phaân tích vector:
Hình treân ta phaân tích a thaønh c theo chieàu vector b vaø e. Theo caùch naøy vector c goïi laø chieáu tröïc giao cuûa a leân b. Roõ raøng c coù cuøng chieàu vôùi b, ta coøn phaûi tính ñoä lôùn | c|.
Theo phöông trình a.b = |a||b|cos() vaø heä thöùc löôïng tam giaùc ta coù phöông trình:
|c| = |a| = a.u (*)
Nhö theá ñoä daøi cuûa c chæ phuï thuoäc vaøo ñoä daøi cuûa a. Baây giôø ta hình thaønh vector c, baèng caùch theâm chieàu cuûa b.
c = |c|.ub
Sau ñoù, keát hôïp vôùi phöông trình (*) treân ta coù:
c = ( a.ub)ub
c = a.b b
|b|2
Ví duï: trong hai chieàu, chieáu cuûa a = (6,4) leân b = (1,2) nhö hình döôùi
c
a
e
b
x
y
Hình chieáu cuûa c naèm daøi hôn b keå töø goác, töø phöông trình treân ta coù ñoä daøi cuûa c laø (2.8, 5.6), vector e = a-c = (3.2, -1.6 ).
Daïng ñieåm chuaån cho ñöôøng vaø maët phaúng
Daïng ñieåm chuaån cho ñöôøng vaø cho maët phaúng duøng nhieàu trong ñoà hoïa nhö vieäc caét loaïi boû ñöôøng bò che vaø toâ ña giaùc.
A
c
n
L
c
n
x
y
Xeùt ñöôøng L ñi qua ñieåm A = (Ax ,Ay) theo chieàu vector c = (cx ,cy), ta coù vector n vuoâng goùc vôùi vector c nghóa laø c.n = 0, cuõng coù nghóa laø c.n + c.n=0, hay: cy / cx = -nx / ny
Ñieàu kieän n tröïc giao vôùi c cho ta suy ra n coù theå laø boäi soá baát kyø cuûa (cx , cy), coù hai chieàu ñoái nhau. Ñeå coù phöông trình cho ñöôøng L, xeùt ñieåm baát kyø R = (x,y) treân L. Vector R phaûi vuoâng goùc vôùi n, neân n.(R-A) = 0. Ta coù theå vieát laïi nhö sau: nR=nA, nhöng khoâng theå nhaân ñieåm vôùi vector ñöôïc. Ta thay vector R baèng r ñi töø goác vaø thay A baèng a. Nhö vaäy, caùc tính toaùn ñeàu phuï thuoäc vaøo vieäc choïn goác toïa ñoä, coøn phöông trình ñöôøng thaúng vaãn phuï thuoäc vaøo goác khoâng coù gì thay ñoåi. Nhö vaäy ta coù:
n.r = D Vôùi D = n.a = nx Ax + ny Ay
Ñaây laø phöông trình ñieåm chuaån cho ñöôøng. Phöông trình naøy coù theå vieát daïng quen thuoäc nhö sau:
nxx + nyy = D
· Môû roäng daïng ñieåm cho maët phaúng
Caùc maët phaúng cuõng coù theå bieåu dieãn ôû daïng chuaån ñieåm. Moät maët phaúng hoaøn toaøn ñöôïc xaùc ñònh vôùi moät ñieåm S = (sx, sy, sz) naèm trong ñoù vaø höôùng chuaån cuûa maët phaúng. Chuaån cho maët phaúng ñöôïc hieåu laø vuoâng goùc vôùi moïi ñöôøng trong maët phaúng. Goïi höôùng chuaån laø n= (nx, ny, nz). Vôùi ñieåm R= (x, y, z) baát kyø trong maët phaúng, xaây döïng vector töø R ñeán S, vuoâng goùc vôùi n.
n.(R-S) = 0
Thay R-S baèng r -s vaø duøng tính tuyeán tính, ta ñöôïc:
n.r = D vôùi D = n.s
Ñaây laø phöông trình ñieåm chuaån cuûa maët phaúng. Moïi ñieåm treân maët phaúng coù cuøng tích voâ höôùng vôùi chuaån. Nghóa laø moïi ñieåm coù cuøng hình chieáu leân n.
Phöông trình maët phaúng P thöôøng vieát laø: Ax + By + Cz = D
Tö ø tích voâ höôùng cuûa phöông trình ta thaáy raèng daïng ñieåm chuaån thöïc ra laø:
nxX + nyY + nz Z = D
Vôùi A = nx, B = ny , vaø C = nz. Ñieàu naøy cho thaáy (A, B, C) laø chieàu chuaån cuûa maët phaúng.
Ñieåm treân maët gaàn goác nhaát laø ñieåm chieáu vuoâng goùc cuûa goác leân maët. Nhö vaäy noù tæ leä vôùi n, goïi laø Kn, neân khoaûng caùch laø| Kn |. Vì Kn naèm treân maët neân n. (Kn)=D.
S
n
Kieåm tra nöûa khoâng gian trong vaø ngoaøi cuûa moät ñieåm
Xeùt ñieåm Q, giaû söû ñöôøng E ñi qua ñieåm A vaø coù chuaån höôùng ra n nhö hình veõ:
n
E
A
inside
E
Goùc giöõa n vaø Q -A 0. Töông töï, goùc seõ lôùn hôn 90 neáu Q naèm phía trong, vì vaäy n.(Q -A) < 0. Cuoái cuøng, = 90 neáu Q naèm treân E, vaø n .(Q - A) = 0. Neáu thay Q -A baèng vector q - a vaø goïi ñaët a.n = D, thì ñöôøng E ñöôïc cho bôûi phöông trình n.p = D, vaø ta vieát laïi thuû tuïc kieåm tra ñieåm Q vôùi vector bieåu dieãn q seõ naèm:
1. ÔÛ nöûa khoâng gian phía ngoaøi cuûa E neáu q.n > D.
2. Treân E neáu p.n = D.
3. ÔÛ nöûa khoâng gian phía trong cuûa E neáu q.n < D.
· Môû roäng cho maët phaúng
Giaû söû maët P qua ñieåm A vaø coù vector chuaån höôùng ra n thì ñieåm Q seõ:
1. ÔÛ nöûa khoâng gian phía ngoaøi cuûa P neáu T=(q-a).n > 0
2. Treân P neáu (q-a).n=0
3. ÔÛ nöûa khoâng gian phía trong cuûa P neáu (q-a).n<0.
Caét ñöôøng thaúng vôùi cöûa soå loài
Ta duøng kieåm tra trong-ngoaøi ñeå xaây döïng coâng cuï caét höõu hieäu vôùi cöûa soå laø ña giaùc loài baát kyø. Cöûa soå W chöùa moät ña giaùc loài cuøng vôùi ñöôøng thaúng L töø P1 tôùi P2. Ta muoán xaùc ñònh phaàn thaáy cuûa L naèm trong W. Ña giaùc loài neân phaàn trong cöûa soå ñöôïc ñònh nghóa laø vuøng naèm ôû nöûa khoâng gian phía trong cuûa moãi caïnh cuûa W. Ñoaïn L ñöôïc kieåm tra ñoái vôùi moãi caïnh cuûa W, vaø phaàn naèm ôû nöûa khoâng gian phía ngoaøi ñöôïc loaïi ra. Sau khi moïi caïnh ñaõ ñöôïc kieåm tra, phaàn coøn laïi cuûa L seõ naèm trong W.Ta bieåu dieãn L ôû daïng tham soá:
P(t) = P1 + ct vôùi c = P2 - P1.
w
L
P
P
Vôùi moãi caïnh cöûa soå, duøng hai giaù trò t vaø t ñeå giöõ laïi vuøng cuûa t maø ñoaïn coù theå naèm trong cöûa soå. Nghóa laø khoâng theå thaáy ñoaïn ôû ngoaøi khoaûng (t, t). Giaù trò baét ñaàu cho t vaø tlaø 0 vaø 1. Khoaûng naøy lieân tuïc ñöôïc caét xeùn khi xöû lyù xong moãi caïnh. Neáu luùc naøo khoaûng naøy thaønh roãng, thoaùt ra khoûi thuaät giaûi caét, vaø ñoaïn L hoaøn toaøn bò caét. Coøn khoâng thì khoaûng (t, t) xaùc ñònh phaàn cuûa L naèm trong cöûa soå. Vì W loài, moãi caïnh E cuûa noù coù theå cho laø ñöôøng cho ôû daïng ñieåm chuaån:
n.p = D
Vôùi n laø chuaån höôùng ra cuûa caïnh. Baây giôø E coù theå coù moät soá tình huoáng so vôùi ñöôøng L.
P
P
P
P
c
c
n
n
E
E
· E song song L: neáu n tröïc giao vôùi c (nghóa laø: n .c= 0). Nhö vaäy L seõ naèm hoaøn toaøn ôû trong hoaëc ôû ngoaøi cöûa soå. Ñeå xeùt tieáp, choïn ñieåm baát kyø treân L, laø P1 vaø kieåm tra trong-ngoaøi. Ñaët p= P - 0 laø vector töø goác toïa ñoä ñeán P. L seõ hoaøn toaøn naèm trong neáu:
p.n < D
Ngöôïc laïi L hoaøn toaøn naèm ngoaøi.
· E khoâng song song vôùi L: L phaûi caét caïnh E taïi ti, ñeå tính ti duøng phöông trình:
ti=( D - n.p1 ) /n.c
Neáu chieàu c cuûa noù nhoû hôn 900 keå töø n ( n.c > 0) thì ñöôøng seõ ñi ra. Ngöôïc laïi seõ ñi vaøo. Neáu ñi vaøo, thì phaàn vôùi t ti seõ khoâng thaáy ñöôïc, vaø t ñöôïc giaûm veà ti(neáu ti < t). Khi keát thuùc, giaù trò cuûa t vaø t seõ ñöôïc thay vaøo P1+ ct, ñeå coù ñöôïc caùc ñieåm ñaàu cuûa ñöôøng bò caét.
Tích hai vector
Tích vector cuûa hai vector laø moät vector. Moät trong nhieàu tính chaát höõu duïng cuûa noù laø noù tröïc giao vôùi hai vector ban ñaàu. Tích vector chæ ñöôïc ñònh nghóa cho vector ba chieàu, nhöng noù cuõng aùp duïng trong moät soá vaán ñeà trong ñoà hoïa lieân quan ñeán ña giaùc hai chieàu.
Cho vector a=(ax, ay, az) vaø b=(bx, by, bz) tích vector cuûa chuùng vieát laø a x b. Noù ñöôïc ñònh nghóa theo caùc vector ñôn vò chuaån i, j, k nhö sau:
a x b = (ay.bz - az.by).i + (az.bx - ax.bz).j + (ax.by - aybx).k
· Töø ñònh nghóa suy ra caùc tính chaát ñaïi soá sau:
1. i x j = k
j x k = i
i x k = j
2. a x b = -b x b
3. a x (b + c) = a x b +a x c
4. (sa) x b = s(a xb)
· YÙ nghóa hình hoïc cuûa tích vector:
1. ax b tröïc giao vôùi caû a vaø b.
2. Ñoä daøi a x b baèng dieän tích hình bình haønh xaùc ñònh bôûi a vaø b. Dieän tích naøy laø:
|a x b| = |a||b|sin()
vôùi laø goùc giöõa a vaø b, ño töø a ñeán b hay ngöôïc laïi mieãn sao goùc nhoû hôn 180.
3. Chieàu cuûa a x b xaùc ñònh töø quy taéc baøn tay phaûi khi laøm vieäc trong heä tay phaûi.
Tích boä ba voâ höôùng
Cho ba vector a, b, c keát hôïp chuùng cho ra soá voâ höôùng nhö sau:
S = a.(b x c) = ax (bycz -bzcy) + ay(bz cx - bxcz ) + az (bxcy - bycx).
Ta co:ù S = a.(b x c) = b.(c x a) = c.(a x b)
Tích boä ba voâ höôùng coù yù nghóa hình hoïc ñôn giaûn. Giaù trò cuûa noù laø theå tích cuûa khoái laêng truï taïo bôûi caùc vector a,b, c. Daáu cuûa tích boä ba voâ höôùng tuøy theo
cos () döông neáu 90.
a x b
Theå tích a x b x c
a
b
c
Phöông trình maët phaúng
Trong khoâng gian, qua 3 ñieåm A (x a, ya, za), B(xb, yb, zb), vaø C(xc, Yc, zc) khoâng thaúng haøng xaùc ñònh ñöôïc phöông trình maët phaúng nhö sau:
Ta coù vector AB = (x-x, y-y, z-z) vaø
AC = (x-x, y-y, z-z)
Tích höõu höôùng cuûa hai vector AB vaø AC laø phaùp vector n cuûa maët phaúng mp(ABC). Vector n coù toïa ñoä nhö sau:
n = ((y-y)*(z-z) - (y-y)*(z-z),
(z-z)*(x-x) - (z-z)*(x-x),
(x-x)*(y-y) - (x-x)*(y-y))
Neáu chuùng ta ñaët:
a = (y-y)*(z-z) - (y-y)*(z-z)
b = (z-z)*(x-x) - (z-z)*(x-x)
c= (x-x)*(y-y) - (x-x)*(y-y)
d = - xa- y b- z c
thì vector n coù theå vieát laïi nhö sau: n = (a, b, c)
Phöông trình maët phaúng ñöôïc xaùc ñònh theo ñònh thöùc caáp 3 nhö sau:
x-x x-x x-x
y-y y-y y-y
z-z z-z z-z
= 0
Phöông trình maët phaúng mp(ABC) ôû daïng toång quaùt:
aX + bY+ cZ + d= 0
Phöông trình ñöôøng thaúng
Trong khoâng gian cho hai ñieåm A (x a , ya , za), B(xb , yb , zb) seõ xaùc ñònh ñöôïc phöông trình ñöôøng thaúng ñi qua hai ñieåm A ,B nhö sau:
Vector AB = (xb - x a , yb - ya , zb -za ) laø vector chæ phöông cuûa ñöôøng thaúng qua hai ñieåm A, B (ñeå goïn hôn ta vieát vector chæ phöông AB=(a1, a2, a3), phöông trình cuûa ñöôøng thaúng coù ba daïng nhö sau:
· Phöông trình tham soá:
X = at + x
Y = at + y
Z = at + y
· Phöông trình daïng chính taéc:
= = (vôùi ñieàu kieän a, a, a 0 )
· Phöông trình daïng toång quaùt:
a2(x - xa ) = a1( y - ya )
a1(z - za ) = a3( x - xa )
Heä phöông trình treân töông ñöông vôùi heä phöông trình sau:
ax - ay + 0 + ay- ax = 0
ax + 0 - az + az - ax = 0
Phöông trình toång quaùt cuûa ñöôøng thaúng qua 2 ñieåm trong khoâng gian laø heä phöông trình baäc nhaát 3 bieán x, y, z nhö treân.
II. CAÙC ÑOÁI TÖÔÏNG HÌNH HOÏC VAØ SÖÏ TÖÔNG QUAN
Trong phaïm vi cuûa moân hình hoïc thì khoâng gian dieãn dòch cuûa noù raát lôùn, chính vì vaäy toâi thieát keá thuaät toaùn treân caùc ñoái töôïng hình hoïc cô baûn. Vaø töø nhöõng thuaät toaùn naøy chuùng ta coù theå môû roäng ra cho moät dieãn dòch roäng lôùn hôn.
II.1. CAÙC QUAN HEÄ HÌNH HOÏC TRONG 2D
Caùc ñoái töôïng hình hoïc cô baûn:
· Ñieåm
· Ñöôøng thaúng
· Ña giaùc
Söï töông quan giöõa caùc ñoái töôïng hình hoïc:
· Ñieåm - Ñöôøng thaúng.
· Ñieåm - Ña giaùc.
· Ñöôøng thaúng - Ñöôøng thaúng.
· Ñöôøng thaúng - Ña giaùc.
· Ña giaùc - Ña giaùc.
Kieåm tra söï töông quan giöõa caùc ñoái töôïng hình hoïc:
Ñieåm - Ñöôøng thaúng
Kieåm tra ñieåm coù thuoäc ñöôøng thaúng?
Tính khoaûng caùch töø ñieåm ñeán ñöôøng thaúng neáu ñieåm khoâng thuoäc ñöôøng thaúng.
Ñieåm - Ña giaùc
Kieåm tra ñieåm beân trong hay beân ngoaøi ña giaùc?.
Ñöôøng thaúng - Ñöôøng thaúng
Kieåm tra hai ñöôøng thaúng truøng nhau, caét nhau hay song song.
Tính goùc giöõa hai ñöôøng thaúng.
Tính hình chieáu cuûa ñoaïn thaúng treân ñöôøng thaúng.
Ñöôøng thaúng - Ña giaùc
Kieåm tra ñöôøng thaúng naèm beân trong hay beân ngoaøi ña giaùc.
Clip moät ñoaïn thaúng vaøo ña giaùc.
Ña giaùc - Ña giaùc
Kieåm tra söï töông quan giöõa hai ña giaùc.
Caét nhau?
Loàng nhau hay rôøi nhau?
Tính dieän tích giao nhau cuûa hai ña giaùc.
Kieåm tra ña giaùc loài, loõm.
Tính dieän tích cuûa ña giaùc.
II.2. CAÙC QUAN HEÄ HÌNH HOÏC TRONG 3D
Caùc ñoái töôïng hình hoïc cô baûn:
· Ñieåm
· Ñöôøng thaúng
· Maët phaúng
Söï töông quan giöõa caùc ñoái töôïng hình hoïc:
· Ñieåm - Ñöôøng thaúng.
· Ñieåm - Maët phaúng.
· Ñöôøng thaúng - Ñöôøng thaúng.
· Ñöôøng thaúng - Maët phaúng.
· Maët phaúng - Maët phaúng.
Kieåm tra söï töông quan giöõa caùc ñoái töôïng hình hoïc:
Ñieåm - Ñöôøng thaúng
Kieåm tra ñieåm coù thuoäc ñöôøng thaúng?
Tính khoaûng caùch töø ñieåm ñeán ñöôøng thaúng neáu ñieåm khoâng thuoäc ñöôøng thaúng.
Ñieåm - Maët phaúng
Kieåm tra ñieåm coù thuoäc maët phaúng?
Tính khoaûng caùch töø ñieåm ñeán maët phaúng neáu ñieåm khoâng thuoäc maët phaúng.
Ñöôøng thaúng - Ñöôøng thaúng
Kieåm tra hai ñöôøng thaúng ñoàng phaúng, caét, song song, cheùo nhau, vuoâng goùc?
Tính goùc giöõa hai ñöôøng thaúng.
Tính khoaûng caùch giöõa hai ñöôøng thaúng cheùo nhau.
Tính hình chieáu cuûa ñoaïn thaúng treân ñöôøng thaúng.
Ñöôøng thaúng - Maët phaúng
Kieåm tra ñöôøng thaúng thuoäc maët phaúng?
Kieåm tra ñöôøng thaúng vaøø maët phaúng caét nhau?
Kieåm tra ñöôøng thaúng vaø maët phaúng song song?
Kieåm tra ñöôøng thaúng vaø maët phaúng vuoâng goùc?
Tính goùc giöõa ñöôøng thaúng vaø maët phaúng neáu ñöôøng thaúng vaø maët phaúng caét nhau.
Tính khoaûng caùch giöõa ñöôøng thaúng vaø maët phaúng neáu ñöôøng thaúng vaø maët phaúng song song nhau.
Maët phaúng - Maët phaúng
Kieåm tra hai maët phaúng truøng nhau?
Kieåm tra hai maët phaúng caét nhau?
Kieåm tra hai maët phaúng song song?
Kieåm tra hai maët phaúng vuoâng goùc?
Tính goùc giöõa hai maët phaúng neáu hai maët phaúng caét nhau.
Tính khoaûng caùch giöõa hai maët phaúng neáu hai maët phaúng song song nhau.
Tìm giao ñieåm cuûa hai maët phaúng.
III. CAÙC THUAÄT TOAÙN KIEÅM TRA SÖÏ TÖÔNG QUAN GIÖÕA CAÙC ÑOÁI TÖÔÏNG HÌNH HOÏC
Trong phaàn naøy toâi trình baøy caùch thöïc hieän moät vaán ñeà, ñöôïc xaây döïng theo logic nhaèm muïc ñích ñeå ngöôøi ñoïc hoaëc tham khaûo coù theå deã daøng kieåm tra so saùnh ñoái chieáu giöõa thuaät toaùn vôùi cô sôû toaùn hoïc.
III.1. CAÙC QUAN HEÄ HÌNH HOÏC TRONG MAËT PHAÚNG (2D)
Tính goùc giöõa hai ñöôøng thaúng
Cô sôû toaùn hoïc:
Ñaây laø öùng duïng quan troïng cuûa tích voâ höôùng. Hình a döôùi cho thaáy goùc q giöõa hai vector a vaø b. Chuùng taïo thaønh hai caïnh cuûa tam giaùc, vaø caïnh thöù ba laø a-b.
b
a
a-b
Töø ñònh nghóa tích voâ höôùng cuûa vector ø vaø laø a.b= |a||b| cos( )
vôùi q :goùc giöõa vector a vaø vector b
Vaø töø bieåu thöùc giaûi tích cuûa tích voâ höôùng:
a.b = a b+ a b
Ta coù cos() = a.b / |a||b|=/
Cos() döông neáu || nhoû hôn 90o, vaø aâm neáu || lôùn hôn 90o.
Giaûi thuaät:
- Tính vector chæ phöông a vaø b cuûa 2 ñoaïn thaúng
- Tính vector voâ höôùng a.b
- Cos ()= a.b / |a| |b|
- Goùc 2 ñoaïn thaúng Alpha= arcos(cos())
Tìm hình chieáu cuûa ñoaïn thaúng AB leân ñöôøng thaúng b
Cô sôû toaùn hoïc:
Ñeå tính hình chieáu ñoaïn AB leân ñöôøng thaúng b ñi qua C vaø D, ta tìm hình chieáu cuûa ñieåm A laø A’ vaø B laø B’ treân ñöôøng thaúng b. Ñoaïn A’B’ chính laø hình chieáu cuûa AB treân ñöôøng b.
A
B
B’
A’
C
D
(b)
· Xaùc ñònh PT ñi qua 2 ñieåm C, D:
ax + by + c = 0
coù vector chæ phöông VCF = (xD-xC , yD-yC ) = (-b, a) vaø c = - a * xC - b * yC.
· Xaùc ñònh PT ñöôøng thaúng D ñi qua ñieåm A vaø vuoâng goùc vôùi CD:
bx -ay + c’ = 0
coù vector chæ phöông cuûa D =(a, b)
vaø c’= b*xA + a*yA
· Tính giao ñieåm A’(xA’, yA’) cuûa heä PT (1) vaø (2)
ax + by + c = 0 (1)
bx - ay + c’= 0 (2)
xA’= (-c’*b + c*a) / ( a*a + b*b)
yA’= ( -c*b + c’*a) / ( a*a + b*b)
· Töông töï tính B’ laø giao ñieåm cuûa:
. Phöông trình ñöôøng thaúng ñi qua CD
. Vaø Phöông trình ñöôøng thaúng D’ ñi qua B vaø vuoâng goùc vôùi CD
Giaûi thuaät:
- Tìm vector chæ phöông VCF (-b, a) cuûa phöông trình ñöôøng thaúng qua hai dieåm C, D: ax + by + c =0
- Tính heä soá c.
- Tính c1 cuûa phöông trình D1 ñi qua ñieåm A vaø vuoâng goùc vôùi CD: bx - ay + c1 = 0
- Tìm giao ñieåm A’cuûa ñöôøng D1 vaø ñöôøng qua C, D .
- Tìm giao ñieåm B’ cuûa ñöôøng D2 ñi qua ñieåm B vaø vuoâng goùc vôùi ñöôøng thaúng CD.
- Khi ñoù A’B’ chính laø hình chieáu cuûa AB.
Xaùc ñònh giao ñieåm giöõa hai ñoaïn thaúng
Cô sôû toaùn hoïc:
Cho hai ñoaïn thaúng, xaùc ñònh chuùng coù caét nhau khoâng, neáu coù tìm giao ñieåm.Giaû söû ñöôøng 1 töø a ñeán b vaø ñöôøng 2 töø c ñeán d nhö trong hình veõ, hai ñoaïn thaúng coù theå boá trí theo nhieàu caùch khaùc nhau.
a
b
c
d
d
c
b
a
b
a
d
c
a
b
c
d
1
2
Phöông trình tham soá cho moãi ñöôøng nhö sau:
(1)
(2)
x1 (t) = ax + (bx - ax) * t
y1 (t) = ay + (by - ay) * t
vaø
x2 (u) = cx + (dx - cx) * u
y2 (u) = cy + (dy - cy) * u
Ta goïi caùc ñöôøng thaúng chöùa caùc ñoaïn thaúng ab vaø cd laø caùc ñöôøng cha, ñaây laø caùc ñöôøng voâ haïn. Tröôùc heát, ta xeùt hai ñöôøng “cha” coù giao nhau khoâng, sau ñoù xem giao ñieåm coù thuoäc caû hai ñoaïn thaúng khoâng? Neáu caùc ñöôøng “cha’ giao nhau, ta coù giaù trò to vaø uo sao cho:
x1 (to) = x2(uo) vaø y1(to) =y2(uo)
Töø ñaây, ta coù caùc phöông trình sau:
(3)
(4)
(5)
ax + (bx - ax) * to = cx + (dx - cx ) * uo
ay + (by - ay) * to = cy + (dy - cy ) * uo
Khöû uo, ta ñöôïc:
D* to = (cx - ax) * (dy - cy ) - (cy - ay) * (dx - cx)
vôùi D = (bx - ax) * (dy - cy) - ( by - ay) * (dx - cx)
Coù hai tröôøng hôïp cô baûn, D baèng hay khaùc 0.
D khaùc zero
Neáu D khaùc 0, ta tính to töø phöông trình (4). Neáu to naèm ngoaøi ñoaïn [0, 1] thì khoâng coù giao ñieåm giöõa hai ñoaïn. Ngöôïc laïi, thì coù theå coù giao ñieåm, thay to vaøo (3) ñeå tính uo. Neáu uo naèm trong ñoaïn [0, 1] thì chaéc chaén coù giao ñieåm, vaø duøng phöông trình (1) vaø (2) ñeå tính.
D baèng zero
(6)
Neáu D baèng 0, töø phöông trình (5) suy ra:
(dy - cy) / (dx - cx) = (by - ay) / (bx - ax)
(7)
Nghóa laø caùc heä soá goùc baèng nhau, neân caùc ñöôøng cha song song. Neáu caùc ñöôøng cha truøng nhau thì caùc ñoaïn cuõng coù theå truøng nhau. Ñeå kieåm ñieàu naøy, ta xem c coù naèm treân ñöôøng cha ñi qua a vaø b khoâng. Döïa vaøo phöông trình cuûa ñöôøng cha laø:
(bx - ax) * (y - ay) - (by - ay) * (x - ax) = 0
thay cx cho x vaø cy cho y vaø xem veá traùi coù ñuû gaàn 0 khoâng (nghóa laø: nhoû hôn löôïng naøo ñoù, nhö 10 - 5). Neáu khoâng, caùc ñöôøng cha khoâng truøng nhau, vaø khoâng coù
giao ñieåm. Neáu thoûa maõn thì phaûi thöïc hieän böôùc kieåm cuoái cuøng ñeå xem caùc ñoaïn coù truøng nhau khoâng.
Töø phöông trình (1) tìm hai giaù trò tc vaø td maø ñöôøng ñaït tôùi vò trí c vaø d. Vì caùc ñöôøng cha truøng nhau, ta chæ caàn duøng thaønh phaàn x (neáu ñöôøng 1 thaúng ñöùng, thì duøng thaønh phaàn y), vaø thay cx vaø dx, ta coù :
(8)
tc = (cx - ax) / (bx - ax)
td = (dx - ax) / (bx - ax)
Ñöôøng 1 baét ñaàu taïi 0 vaø keát thuùc taïi 1, vaø xeùt thöù töï cuûa boán giaù trò 0, 1, tc vaø td, ta xaùc ñònh ñöôïc vò trí töông ñoái cuûa hai ñöôøng. Seõ choàng nhau tröø khi caû hai tc vaø td nhoû hôn 0 hay lôùn hôn 1. Neáu coù truøng nhau, ta deã daøng xaùc ñònh caùc ñieåm ñaàu truøng nhau töø tc vaø td.
Giaûi thuaät ñöôïc xaây döïng trong thuû tuïc Intersect (), goàm caùc tham soá laø boán ñieåm ñaàu cuûa caùc ñöôøng, giaù trò traû veà coù theå coù theå coù caùc giaù trò sau:
1: coù moät giao ñieåm.
2: khoâng giao nhau.
3: caùc ñoaïn thaúng song song nhau.
4: hai ñoaïn thaúng choàng nhau.
5: hai ñoaïn thaúng cuøng naèm treân 1 ñöôøng thaúng, khoâng caét nhau.
Giaûi thuaät:
-Tính Maãu soá D;
-Neáu D 0
. Tính to,uo;
. Neáu to thuoäc [0,1] vaø uo thuoäc [0,1]
+ Tính giao ñieåm M
+ Return 1; ( 2 ñoaïn thaúng caét nhau taïi M)
Ngöôïc laïi Return 2; (2 doaïn thaúng khoâng caét nhau)
- Ngöôïc laïi,
. Neáu c naèm treân ñoaïn ab
+ Tính tc, td;
+ Neáu khoâng phaûi caû tc vaø td 1
Return 4; (2 doaïn thaúng choàng nhau)
+ Ngöôïc laïi,
Return 5; (2ñoaïn thaúng naèm treân 1 ñöôøng thaúng vaø khoâng caét nhau)
. Ngöôïc laïi, Return 3; (2 ñoaïn thaúng song song )
Veõ ña giaùc (Polygon)
Cô sôû toaùn hoïc:
Ña giaùc laø taäp hôïp caùc ñoaïn thaúng lieân tieáp cuøng naèm trong maët phaúng kheùp kín. Moät ña giaùc coù ít nhaát 3 caïnh. Nhö vaäy, ña giaùc ñôn giaûn nhaát laø tam giaùc.
Giaûi thuaät:
- Xuaát phaùt töø ñænh ñaàu tieân
- Veõ noái ñeán ñænh keá tieáp theo thöù töï cuøng chieàu kim ñoàng hoà.
- Veõ noái töø ñænh cuoái cuøng ñeán ñænh ñaàu tieân.
Veõ n-giaùc
Cô sôû toaùn hoïc:
Moät n-giaùc laø ña giaùc quy taéc coù N caïnh (ña giaùc quy taéc: ña giaùc maø moïi caïnh coù ñoä daøi baèng nhau, vaø caùc caïnh keà nhau taïo neân nhöõng goùc trong baèng nhau).
Neáu cho ñænh ñaàu tieân treân truïc x taïi (R, x). Cho goùc A baát kyø, vò trí (x,y) cuûa moät ñieåm treân ñöôøng troøn coù goùc A seõ ñöôïc tính (x,y) = (R cos(A), R sin(A)). Vaø ñænh thöù i, V, cuûa n -giaùc naèm ôû goùc 2p (i -1) / N vaø coù vò trí:
V = ( R cos(2p (i -1) / N ), R sin(2p (i -1) / N) ).
Giaûi thuaät:
- Soá ñænh = N
- Ñònh goùc A = 2 Pi / N
- Voøng laëp xaùc ñònh ñænh thöù i
. Goùc = i *A;
. Tìm toïa ñoä ñænh V.
Toâ maøu ña giaùc
Cô sôû toaùn hoïc:
Phöông phaùp hieån thò caùc vuøng ñöôïc toâ maøu trong ñoà hoïa maùy tính laø quaù trình xaùc ñònh caùc pixel töông öùng thuoäc vuøng toâ maøu cho noù. Coù nhieàu thuaät toaùn ñaõ ñöôïc nghieân cöùu vaø phaùt trieån cho vieäc hieån thò caùc vuøng ñöôïc toâ maøu treân maøn hình, moät trong nhöõng thuaät toaùn ñoù laø toâ maøu theo veát daàu loang, moät thuaät toaùn khaùc laø toâ maøu theo doøng queùt. ÔÛ ñaây ta duøng phöông phaùp toâ maøu theo doøng queùt (scan-line algorithm) hay coøn goïi laø giaûi thuaät toâ maøu chaün leû (odd - even algorithm).
Thuaät giaûi naøy söû duïng caùc giao ñieåm giöõa caùc ñöôøng bieân cuûa vuøng caàn toâ vôùi caùc ñöôøng thaúng goïi laø doøng queùt vaø xaùc ñònh caùc pixel naøo naèm trong vuøng toâ maøu giöõa hai giao ñieåm lieân tieáp, ñoù chính laø caùc pixel doïc theo ñöôøng queùt naèm giöõa hai giao ñieåm vaø naèm beân trong ña giaùc.
ÔÛ moãi ñieåm giao doøng queùt chuyeån ñoåi hoaëc ñi vaøo hoaëc ñi ra khoûi ña giaùc, ñoù laø söï thay ñoåi parity cuûa ñieåm ñoù. Neáu doøng queùt ñi vaøo trong ña giaùc nhöõng pixels tieáp theo seõ ñöôïc toâ, neáu ñi ra ngoaøi nhöõng pixels tieáp theo seõ khoâng ñöôïc toâ.
Khi doøng queùt ñi qua moät ñænh P cuûa ña giaùc (chính laø giao ñieåm cuûa 2 caïnh cuûa ña giaùc) noù taïo ra 2 giao ñieåm, moãi ñieåm vôùi 1 caïnh cuûa ña giaùc ñi qua ñænh ñoù, neáu ñænh ôû giaù trò cöïc (local extremum) Pixels ôû beân traùi vaø beân phaûi cuûa ñænh ñoù seõ coù cuøng parity, nhöng neáu ñænh khoâng ôû giaù trò cöïc caùc Pixels ôû beân traùi vaø beân phaûi cuûa ñænh ñoù seõ coù parity ngöôïc nhau, do ñoù ta caàn coù moät xöû lyù ñaëc bieät hôn.
1
2, 3
1
4
2
Scan line 1
Scan Line 2
Neáu P laø giao ñieåm cuûa hai caïnh coù höôùng y ngöôïc nhau (moät caïnh coù giaù trò y taêng,moät caïnh coù giaù trò y giaûm - Scan Line 1) thì doøng queùt coù 2 ñieåm giao.
Neáu P laø giao ñieåm cuûa hai caïnh coù höôùng y truøng nhau (hai caïnh ñeàu coù giaù trò y cuøng taêng hay giaûm - Scan Line 2) thì doøng queùt coù 1 ñieåm giao.
Tröôùc khi toâ maøu, ta caàn kieåm tra moãi ñænh ña giaùc. Neáu y cuûa noù khoâng laø giaù trò cöïc trò(local extremum), nhö trong scan line 2. Vì nhöõng Pixels ñoái vôùi beân traùi vaø phaûi cuûa ñænh ñoù khaùc parity, khaùc giaù trò kieåm tra inside-outside; ta phaûi laøm ngaén moät trong hai caïnh ñi moät chuùt (giaûm y cuûa ñaàu caïnh ñoù moät pixel).
Ñoái vôùi caïnh naèm ngang trong ña giaùc khoâng caàn ñöa vaøo taäp caùc caïnh cuûa ña giaùc ñeå xöû lyù.
Giaûi thuaät:
Böôùc 1: Xaùc ñònh Frame “bao” ña giaùc.
Frame bao ña giaùc laø hình chöõ nhaät nhoû nhaát chöùa toaøn boä ña giaùc. Ñeå xaùc ñònh hình chöõ nhaät naøy ta laáy min hoaëc max caùc toïa ñoä ñænh cuûa ña giaùc trong heä toïa ñoä Descartes roài taêng, hoaëc giaûm 1 ñeå ñaûm baûo hình chöõ nhaät laø hình bao vaø ña giaùc hoaøn toaøn naèm trong noù.
Böôùc 2: Xaùc ñònh danh saùch caùc caïnh ña giaùc ñeå xöû lyù.
Laàn löôït duyeät taát caû caïnh cuûa ña giaùc:
· Khoâng ñöa caïnh naèm ngang cuûa ña giaùc vaøo danh saùch.
· Kieåm tra 2 caïnh ña giaùc lieân tieáp, neáu ñænh chung khoâng laø ñieåm cöïc trò (local extremum), laøm ngaén ñaàu caïnh cuûa moät caïnh ñi qua ñænh chung moät pixel.
Böôùc 3: Tieán haønh toâ maøu.
Tieán haønh caùc ñöôøng queùt ngang tö ø Ymin + 1 ñeán Ymax - 1.
· ÖÙng vôùi moät ñöôøng queùt ngang yi naøo ñoù, ta xaùc ñònh caùc ñieåm caét (baèng giaûi thuaät tìm giao ñieåm giöõa hai ñoaïn thaúng ñaõ coù), giöõa caùc ñöôøng queùt ngang vôùi taát caû caùc caïnh cuûa ña giaùc. Vì tung ñoä y cuûa ñieåm caét baèng yi neân ta chæ caàn ñöa caùc hoaønh ñoä xi cuûa ñieåm caét vaøo moät danh saùch.
· Saép xeáp laïi danh saùch sao cho caùc giaù trò xi taêng daàn.
· Duyeät qua caùc ñieåm caét vaø ñeám soá ñieåm caét ñaõ duyeät.
· Neáu ñieåm caét truøng vôùi ñænh cuûa ña giaùc: Neáu coù moät caïnh song song vôùi ñöôøng queùt thì ñænh tröôùc ñeám taêng vaø ñænh sau khoâng ñeám taêng.
· Toâ maøu giöõa caùc caëp giao ñieåm .
Böôùc 4: Laäp laïi böôùc hai cho ñeán khi yi = ymax.
Böôùc 5: Veõ laïi ña giaùc baèng maøu ñaõ toâ.
Löu yù: Neáu ña giaùc khoâng phaûi laø ña giaùc ñôn thì giaûi thuaät naøy khoâng vaän duïng ñöôïc.
Ñieåm beân trong / beân ngoaøi ña giaùc
Cô sôû toaùn hoïc:
Giaûi thuaät naøy nhaèm xaùc ñònh moät ñieåm cho tröôùc coù naèm beân trong moät ña giaùc ñôn phaúng hay khoâng.
Giaûi thuaät xaây döïng döïa treân ñònh lyù mang teân JORDAN sau ñaây:
“Moãi ñöôøng cong, kín, ñôn, phaúng, moät chieàu, phaân hoaïch maët phaúng thaønh hai mieàn, moät trong hai mieàn ñoù hoaøn toaøn chöùa nhöõng ñöôøng thaúng naøo ñoù, mieàn coøn laïi thì khoâng coù tính chaát ñoù”.
Trong ñònh lyù treân ñaây moät trong hai mieàn seõ ñöôïc goïi laø mieàn trong (goàm baûn thaân ñöôøng cong vaø phaàn maët phaúng giôùi noäi bôûi ñöôøng cong). Khoâng thuoäc mieàn trong goïi laø mieàn ngoaøi.
Ñònh lyù naøy vaãn ñuùng cho tröôøng hôïp ña giaùc ñôn phaúng moät chieàu nhö laø moät tröôøng hôïp rieâng.
Töø ñònh lyù naøy daãn ñeán heä quaû sau:
“Töø moät ñieåm P baát kyø, veõ moät tia chæ caét ña giaùc ôû nhöõng ñieåm trong cuûa caùc caïnh (nghóa laø : khoâng ñi qua ñænh naøo cuûa ña giaùc); neáu soá giao ñieåm laø leû thì P laø ñieåm trong, neáu soá giao ñieåm laø chaün thì P laø ñieåm ngoaøi”.
Veà maët kyõ thuaät moïi ñöôøng cong ñôn, phaúng, kín, lieân thoâng, khoâng töï caét ñeàu coù theå tieáp caän tuyeán tính baèng moät ña giaùc bao goàm moät soá höõu haïn caùc caïnh lieân tieáp. Vì vaäy cho pheùp xaây döïng moät giaûi thuaät test quan heä trong/ ngoaøi chæ baèng caùch xeùt soá giao ñieåm cuûa tia coù goác laø ñieåm caàn xeùt.
Giaûi thuaät:
- Choïn Px laø nöûa ñöôøng thaúng xuaát phaùt töø P song song vôùi truïc Ox, höôùng veà phía x>0. Laáy P=(x,y).
- P laø ñieåm caàn xeùt.
- Neáu (P laø moät ñænh) hoaëc (P thuoäc trong moät caïnh) thì
Return (P ñieåm trong)
- Ngöôïc laïi, xaùc ñònh giao ñieåm Px vôùi caùc caïnh ña giaùc
{
. Ci laø caïnh Pi Pi+1 cuûa ña giaùc
. Neáu y = yi thì xeùt hai caïnh coù moät ñaàu laø Pi (1)
.. Neáu caû hai ñaàu kia ôû moät phía cuûa Pi thì tính Px caét caû hai caïnh
. Ngöôïc laïi (1)
Neáu y > Max(yi,yi+1) hay y<Min(yi,yi+1) (2)
Thì Px khoâng caét caïnh Ci
. Ngöôïc laïi (2)
.. Neáu x <= Min (xi,xi+1) (3)
Thì Py caét caïnh Ci
. Ngöôïc laïi (3)
.. Xeùt toïa ñoä giao ñieåm (yo,xo) cuûa Px vôùi caïnh Ci
Neáu x >= xo thì Px khoâng caét Ci
}
- Neáu soá giao ñieåm leû
. Return P thuoäc ña giaùc.
Kieåm tra quan heä giöõa ñoaïn thaúng vaø ña giaùc
Caùc chöông trình öùng duïng moâ taû caùc hình aûnh baèng heä toïa ñoä theá giôùi thöïc, coù theå laø baát kyø heä toïa ñoä Descartes naøo maø ngöôøi duøng caûm thaáy thuaän tieän nhaát. Caùc hình aûnh ñöôïc moâ taû trong heä toïa ñoä thöïc sau ñoù seõ ñöôïc caùc heä ñoä hoïa aùnh xaï vaøo caùc heä toïa ñoä thieát bò. Thoâng thöôøng, caùc heä ñoà hoïa cho pheùp ngöôøi duøng xaùc ñònh moät vuøng naøo ñoù cuûa hình aûnh ñöôïc hieån thò vaø noù seõ hieån thò ôû ñaâu treân maøn hình (viewport). Ta coù theå choïn moät vuøng hay nhieàu vuøng ñeå hieån thò, caùc vuøng naøy coù theå ñaët ôû caùc nôi khaùc nhau hay loàng vaøo nhau treân maøn hình. Quaù trình naøy ñoøi hoûi nhieàu thao taùc nhö dòch chuyeån, bieán ñoåi tyû leä ñeå ñöa vaøo beân trong viewport hoaëc ñôn giaûn laø loaïi boû caùc phaàn hình aûnh naèm ngoaøi vuøng ñang ñöôïc xeùt. Thao taùc cuoái cuøng vaø cuõng ñöôïc söû duïng nhieàu nhaát coøn ñöôïc goïi laø clipping. Trong thuaät ngöõ thoâng thöôøng Viewport ñöôïc hieåu nhö moät window (hình chöõ nhaät) theo ñoù hình aûnh ñöôïc clipping. Tuy nhieân Viewport cuõng coù theå laø moät ña giaùc baát kyø. Baøi toaùn clipping sau ñaây ñöôïc xeùt cho tröôøng hôïp toång quaùt hôn: clipping vôùi ña giaùc ñôn baát kì (cho caû hai tröôøng hôïp ña giaùc loài hoaëc loõm).
Cô sôû toaùn hoïc vaø giaûi thuaät:
Caùc böôùc tieán haønh clipping ñoaïn thaúng AB baèng moät ña giaùc ñôn, phaúng baát kì nhö sau:
Böôùc 1: Hoaùn ñoåi A, B ñeå xA < xB.
Neáu xA = xB . Hoaùn ñoåi A,B ñeå yA < yB
Böôùc 2: Kieåm tra tính trong ngoaøi cuûa A vaø B ñoái vôùi ña giaùc
(Duøng giaûi thuaät kieåm tra ñieåm beân trong/ngoaøi ña giaùc )
Böôùc 3: Tìm giao ñieåm cuûa AB vôùi ña giaùc
(Duøng giaûi thuaät xaùc ñònh giao ñieåm cuûa 2 ñoaïn ñaõ coù )
Neáu coù giao ñieåm thì
{
- Ñöa caùc toïa ñoä cuûa caùc ñieåm caét vaøo moät danh saùch
- Saép xeáp cho hoaønh ñoä caùc giao ñieåm taêng daàn
(Neáu xA = xB saép xeáp theo tung ñoä)
}
Böôùc 4: Thöïc hieän clipping.
- Neáu A vaø B ñeàu naèm trong ña giaùc thì (1)
Neáu soá ñieåm caét = 0, Return (AB naèm hoaøn toaøn trong ña giaùc)
- Ngöôïc laïi
{
. Ñoaïn thaúng töø A ñeán ñieåm caét thöù 1 thuoäc ña giaùc.
. i = 1
. Laëp laïi
. Tìm trung ñieåm cuûa ñoaïn thaúng noái hai ñieåm caét keá tieáp nhau.
. Kieåm tra trong /ngoaøi ñoái vôùi trung ñieåm.
. Neáu trung ñieåm naèm trong ña giaùc thì
Return (Ñoaïn thaúng thuoäc ña giaùc)
. Ngöôïc laïi, Return (Ñoaïn thaúng khoâng thuoäc ña giaùc).
. Inc (i,1)
Cho ñeán khi i = soá ñieåm caét
}
- Ngöôïc laïi, coù ñieåm A hay B naèm ngoaøi ña giaùc (1)
- Neáu soá ñieåm caét = 0, Return (Ñoaïn AB naèm ngoaøi ña giaùc).
- Neáu soá ñieåm caét 0 thì
{
. Theâm toïa ñoä ñieåm A vaøo ñaàu danh saùch
. Theâm toïa ñoä ñieåm B vaøo cuoái danh saùch
. i = 1
. Laëp laïi
. Tìm trung ñieåm cuûa ñoaïn thaúng noái hai ñieåm caét keá tieáp nhau
. Kieåm tra trong/ ngoaøi ñoái vôùi trung ñieåm.
. Neáu trung ñieåm naèm trong ña giaùc thì
Return (Ñoaïn thaúng thuoäc ña giaùc)
. Ngöôïc laïi, Return (Ñoaïn thaúng khoâng thuoäc ña giaùc)
. inc (i,1)
Cho ñeán khi heát danh saùch
}
Ngöôïc laïi, Return (Ñoaïn thaúng khoâng thuoäc ña giaùc).
Böôùc 5: Veõ laïi caùc ñoaïn thaúng thuoäc ña giaùc
* Môû roäng: Giaûi thuaät coù theå ñöôïc môû roäng cho vieäc clipping moät ña giaùc baèng caùch thöïc hieän clipping taát caû caùc caïnh cuûa ña giaùc.
Kieåm tra quan heä hai ña giaùc
Cô sôû toaùn hoïc:
Giaûi thuaät naøy cho pheùp clip baát kyø moät ña giaùc vaøo 1 ña giaùc. Noù cuõng cho pheùp hình thaønh söï giao, hoäi cuûa 2 ña giaùc.Chuùng ta baét ñaàu baèng ví duï minh hoïa trong hình sau. Ta lieät keâ nhöõng ñænh theo thöù töï töø traùi sang phaûi, theo chieàu kim ñoàng hoà.
D
6
5
4
3
2
1
d
c
b
a
C
B
A
Hai ña giaùc SUBJ vaø CLIP ñöôïc theå hieän baèng 2 danh saùch (a,b,c,d) vaø (A,B,C,D) töông öùng. Taát caû ñieåm giao cuûa 2 danh saùch seõ ñöôïc xaùc ñònh vaø löu vaøo danh saùch (theo thöù töï sang phaûi cuûa moãi caïnh).
Döïa vaøo hình veõ treân, ta coù:
SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6
CLIP_LIST: A, 6 ,3 , 2, B, C, D, 4, 5
Duyeät SUBJ theo höôùng ñi tôùi cho tôùi khi tìm ñöôïc 1 ñieåm giao ñi vaøo (entering intersection), laø ñieåm giao maø SUBJ di chuyeån töø ngoaøi vaøo trong ña giaùc CLIP.Vaø ñöa ñieåm naøy vaøo danh saùch xuaát ña giaùc ñöôïc clip.
Duyeät SUBJ tôùi khi gaëp 1ñieåm giao khaùc. Nhaûy ra khoûi SUBJ vaø di chuyeån theo CLIP thay vì SUBJ. Duyeät CLIP theo höôùng ñi tôùi. Tôùi khi gaëp moät ñieåm giao, nhaûy ra khoûi CLIP vaø duyeät theo SUBJ theo höôùng ñi tôùi, vaø cöù tieáp tuïc nhö vaäy. Moãi ñænh hoaëc moãi ñieåm giao gaëp phaûi khi duyeät seõ ñöôïc ñöa vaøo danh saùch xuaát ña giaùc ñöôïc clip. Laëp laïi tieán trình treân giöõa 2 ña giaùc, duyeät moãi ña giaùc theo höôùng ñi tôùi cho tôùi khi ñænh ñaàu tieân ñöôïc gaëp laïi. Danh saùch xuaát ra ôû thôøi ñieåm naøy (1,b,2,B)
1 b 2 3 4 d 5 6
a
a
restart
start
SUBJ_LIST:
SUBJ_LIST:
A 6 3 2 B 1 C D 4 5
Baây giôø, ta kieåm tra moät ñieåm giao“entering” khaùc cuûa SUBJ. Vaø seõ taïo ra danh saùch xuaát (3,4,5,6). Vieäc kieåm tra nhöõng ñieåm giao “entering” khaùc seõ chæ ra laø taát caû chuùng ñaõ ñöôïc duyeät, quaù trình chaám döùt.
Caùch thöùc ñeå hieän thöïc quaù trình xöû lyù naøy laø xaây döïng hai danh saùch
SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6
CLIP_LIST : A, 6, 3, 2, B,1, C, D, 4 , 5
Maø trong ño,ù vieäc duyeät moãi ña giaùc vaø lieät keâ nhöõng ñænh vaø ñieåm giao phaûi theo thöù töï ñöôïc gaëp.
Giaûi thuaät:
-Böôùc 1: Taïo danh saùch SUBJ_LIST
Duyeät laàn löôït moãi caïnh ña giaùc SUBJ theo thöù töï cuøng chieàu kim ñoàng hoà
{
- Tìm caùc ñieåm caét cuûa caïnh Pi-Pi+1 vôùi ña giaùc CLIP.
- Saép xeáp danh saùch ñieåm caét theo hoaønh ñoä taêng daàn . Neáu hoaønh ñoä Pi.x=Pi+1.x thì saép xeáp theo tung ñoä.
- Ñöa ñænh Pi vaøo danh saùch SUBJ_LIST
- Ñöa caùc ñieåm caét töø danh saùch ñieåm caét vaøo SUBJ_LIST theo höôùng ñi töø Pi tôùi Pi+1
}
-Böôùc 2: Taïo danh saùch CLIP_LIST
Duyeät laàn löôït moãi caïnh ña giaùc CLIP theo thöù töï cuøng chieàu kim ñoàng hoà
{
- Tìm caùc ñieåm caét cuûa caïnh Pi- Pi+1 vôùi ña giaùc SUBJ.
- Saép xeáp danh saùch ñieåm caét theo hoaønh ñoä taêng daàn. Neáu hoaønh ñoä Pi.x=Pi+1.x saép xeáp theo tung ñoä.
- Ñöa ñænh Pi vaøo danh saùch CLIP_LIST.
- Ñöa caùc ñieåm caét töø danh saùch ñieåm caét vaøo CLIP_LIST theo höôùng ñi töø Pi tôùi Pi+1.
}
-Böôùc 3: Duyeät danh saùch SUBJ_LIST vaø CLIP_LIST.
Voøng laëp (1)
Voøng laëp (2)
- Tìm ñieåm giao “entering” chöa duyeät cuûa SUBJ_LIST.
- Duyeät treân SUBJ_LIST tôùi khi thaáy ñieåm giao tieáp theo .
- Chuyeån sang duyeät treân CLIP_LIST tôùi khi thaáy ñieåm giao tieáp theo.
Cho tôùi khi ñieåm ñaàu tieân(ñieåm ‘entering’) ñöôïc gaëp laïi. (voøng laëp 2 )
- Xuaát Danh saùch ña giaùc tìm ñöôïc ôû treân.
Cho tôùi khi taát caû caùc ñieåm giao ‘entering’ ñaõ ñöôïc duyeät (voøng laëp 1)
Kieåm tra tính loài cuûa ña giaùc
Cô sô ûtoaùn hoïc:
-Nhaän bieát quay traùi vôùi quay phaûi: Coù nhöõng thuaät giaûi ta phaûi duyeät moät ña giaùc, laàn löôït thaêm moãi ñænh hay caïnh. Ta xem nhö di chuyeån theo moät caïnh töø ñænh naøy ñeán ñænh kia vaø sau ñoù ra caïnh keá. Nhö vaäy caàn phaûi bieát ñi theo chieàu phaûi hay traùi.
Ví duï, neáu P1, P2, P3 laø ba caïnh keà nhau cuûa ña giaùc, ta taïo vector caïnh a=P2-P1 vaø b=P3- P2. Hình (1) cho thaáy tröôøng hôïp a vaø b naèm trong maët xy vaø quay traùi khi ñi töø a ñeán b. Coøn hình (2) laø quay phaûi.
b
a
b
a
Hình 1 Hình 2
Giaû söû duøng heä tay phaûi ôû hình 1 vaø hình 2 neân truïc z (hay chieàu k) höôùng ra ngoaøi töø trang saùch tôùi chuùng ta. Duøng quy taéc tay phaûi, tích a x b chæ ra ngoaøi vôùi thaønh phaàn k döông. Neáu laäp tích voâ höôùng vector naøy vôùi chính k, seõ ñöôïc moät ñaïi löôïng maø daáu cuûa noù cho bieát chieàu quay, döông neáu quay traùi vaø aâm neáu quay phaûi. Cho vector a vaø b trong maët xy, quay töø a ñeán b seõ laø döông neáu
T= k.(a x b) >= 0
vaø aâm neáu ngöôïc laïi (Keát quaû khoâng ñoåi ñoái vôùi heä tay traùi).
Vôùi ña giaùc loài, moïi pheùp quay coù cuøng chieàu, nhö ña giaùc A. Neáu ña giaùc khoâng loài, nhö tröôøng hôïp B, goàm caû hai pheùp quay. Nhö vaäy, ña giaùc ñôn laø loài neáu vaø chæ neáu moïi pheùp quay coù coù cuøng daáu khi ñöôïc duyeät.
A
B
Giaûi thuaät:
- Duyeät ña giaùc theo thöù töï caùc ñænh ñeå xeùt vieäc quay töø caïnh a ñeán caïnh b taïi moãi ñænh laø quay phaûi hay quay traùi.
.Tính toïa ñoä theo höôùng oz cuûa tích vector a x b
T= k(a x b) = ax*by - ay*bx
- Neáu moïi pheùp quay ñeàu nhö pheùp quay taïi ñænh thöù nhaát, ña giaùc loài.
- Neáu coù moät pheùp quay khaùc pheùp quay taïi ñænh thöù nhaát,ña giaùc loõm.
Tính dieän tích ña giaùc
Cô sôû toaùn hoïc:
Vieäc tính moät ña giaùc ñôn phaúng baát kyø xuaát phaùt töø vieäc tính dieän tích tam giaùc. Dieän tích tam giaùc ñöôïc tính döïa vaøo tích hai vector nhö sau:
S =(1/2) |a x b|
Trong ñoù caùc vector a, b laø caùc vector caïnh cuûa tam giaùc.
P
P
P
P
P
P
Vôùi moät ña giaùc n ñænh, ta coù theå phaân thaønh n - 2 tam giaùc baèng caùch töø moät ñænh naøo ñoù cuûa tam giaùc ta veõ caùc caïnh noái ñeán taát caû caùc caïnh coøn laïi cuûa ña giaùc. Khi ñoù dieän tích ña giaùc baèng toång dieän tích cuûa caùc tam giaùc con naøy. Laáy ñænh P1 laøm choát, laäp (n-1) vector choát vector a1=P2 - P1, a2 = P3 - P1, an-1=Pn - P1. Caùc vector naøy duøng ñeå tính dieän tích moãi tam giaùc. Hai caïnh cuûa tam giaùc i ñöôïc xaùc ñònh bôûi hai vector ai vaø ai+1.
Nhöng neáu ña giaùc laø loõm, thì khoâng phaûi moïi ña giaùc ñeàu coù dieän tích döông. Do ñoù ñeå hình thaønh coâng thöùc toång quaùt tính dieän tích moät ña giaùc baát kyø ta phaûi bieán ñoåi coâng thöùc tính dieän tích tam giaùc moät chuùt.
Trong coâng thöùc tính dieän tích tam giaùc treân, thay vì duøng trò tuyeät ñoái cuûa tích hai vector, ta nhaân noù vôùi un, chuaån höôùng (ñoä daøi ñôn vò) ra cuûa maët chöùa ña giaùc (neáu ña giaùc naèm trong maët xy, un laø k). Vector chuaån höôùng ra cuûa maët chöùa ña giaùc ñöôïc xaùc ñònh baèng caùch tính tích höõu höôùng hai vector caïnh cuûa tam giaùc. Nhaân vôùi chuaån höôùng ra un laø ñeå loïc ra dieän tích aâm vaø dieän tích döông, noù khoâng aûnh höôûng ñeán baûn thaân töøng dieän tích tam giaùc. Luùc naøy dieän tích tam giaùc ñöôïc tính theo coâng thöùc:
S = (ax.by-ay.bx)/ 2
trong ñoù a, b laø hai vector caïnh cuûa tam giaùc.
Khi ñoù dieän tích cuûa ña giaùc laø:
S =
trong ñoù Si laø dieän tích (coù daáu) cuûa tam giaùc thöù I
Giaûi thuaät:
- i baét ñaàu = 2
- Dieän tích ña giaùc = 0
- Laëp laïi
{
. Tính dieän tích tam giaùc coù 3 ñænh laø : ñænh 1,ñænh i, ñænh i+1
. Dieän tích ña giaùc = Dieän tích ña giaùc + Dieän tích tam giaùc
. Inc (i,1)
}
Cho ñeán khi i=N-1
- Dieän tích ña giaùc = Abs (dieän tích ña giaùc)
III.2. CAÙC QUAN HEÄ HÌNH HOÏC TRONG KHOÂNG GIAN (3D)
1- Caùc pheùp bieán hình 3 chieàu
Cô sôû toaùn hoïc:
Moät trong nhöõng öu ñieåm quan troïng cuûa ñoà hoïa laø cho pheùp deã daøng taùc ñoäng leân caùc ñoái töôïng ñoà hoïa. Taát caû caùc bieán ñoåi treân ñoà hoïa maùy tính ñeàu coù theå thoûa maõn moät caùch töông ñoái deã daøng vì caùc hình aûnh khi ñöa vaøo xöû lyù ñaõ ñöôïc soá hoaù, do ñoù noù coù theå thay ñoåi deã daøng baèng caùc pheùp bieán ñoåi toaùn hoïc. Pheùp bieán ñoåi hình hoïc thöôøng ñöôïc duøng laø pheùp bieán ñoåi Affine.
Coù hai quan ñieåm veà pheùp bieán ñoåi, ñoù laø:
Bieán ñoåi ñoái töôïng.
Bieán ñoåi heä toïa ñoä.
Bieán ñoåi ñoái töôïng: laø thay ñoåi toïa ñoä caùc ñieåm moâ taû noù theo moät quy luaät naøo ñoù.
Bieán ñoåi heä toïa ñoä: seõ taïo ra moät heä toïa ñoä môùi vaø taát caû caùc ñieåm moâ taû ñoái töôïng seõ ñöôïc chuyeån veà heä toïa ñoä môùi naøy. Phaàn naøy ta seõ moâ taû moät soá pheùp bieán ñoåi ñoái töôïng.
Pheùp bieán ñoåi affine 3D bieán ñoåi ñieåm P(Px,Py,Pz) thaønh ñieåm Q:
Q = PM
m m m m
m m m m
m m m m
m m m m
M =
Vôùi P = (Px, Py, Pz), Q = (Qx, Qy, Qz) vaø M laø ma traän bieán hình 4x4
Moät soá pheùp bieán ñoåi Affine cô sôû, ñoù laø: pheùp tònh tieán, pheùp co daõn, pheùp quay.
a/ Pheùp tònh tieán: Dòch chuyeån ñoái töôïng töø vò trí naøy sang vò trí khaùc. Tònh tieán vôùi caùc ñoä dôøi tx, ty, tz.
M =
1 0 0 0
0 1 0 0
0 0 1 0
tx ty tz 1
b/Pheùp co daõn: Vôùi heä soá co Sx , Sy, Sz. Ma traän M laø
Sx 0 0 0
0 Sy 0 0
0 0 Sz 0
0 0 0 1
M =
c/Pheùp quay quanh truïc x goùcA: Toïa ñoä x cuûa vaät theå khoâng ñoåi. Ma traän M laø
1 0 0 0
0 cos(A) sin(A) 0
0 -sin(A) cos(A) 0
0 0 0 1
M =
d/Pheùp quay quanh truïc y goùc A: Toïa ñoä y cuûa vaät theå khoâng ñoåi. Ma traän M laø:
cos(A) 0 -sin(A) 0
0 1 0 0
sin(A) 0 cos(A) 0
0 0 0 1
M =
e/Pheùp quay truïc z goùcA: Toïa ñoä z cuûa vaät theå khoâng ñoåi. Ma traän M laø
cos(A) sin(A) 0 0
-sin(A) cos(A) 0 0
0 0 1 0
0 0 0 1
M =
* Toång hôïp caùc pheùp bieán hình
Pheùp bieán hình T1: PàQ’ coù ma traän M1.
Pheùp bieán hình T2 : Q’àQ coù ma traän M2.
Toång hôïp 2 pheùp bieán hình T1, T2 laø pheùp bieán hình T: PàQ
Pheùp bieán hình T coù ma traän M = M1 x M2
Giaûi thuaät:
- Tính caùc phaàn töû cuûa ma traän M.
- Xaùc ñònh caùc ñieåm môùi cuûa ñoái töôïng qua pheùp bieán hình.
-Veõ laïi ñoái töôïng.
2- Bieåu dieãn ñoái töôïng 3D
Cô sôû toaùn hoïc:
Caùc ñoái töôïng trong theá giôùi thöïc haàu heát laø caùc ñoái töôïng 3D. Vieäc bieåu dieãn caùc ñoái töôïng 3D treân maët phaúng 2D, baèng maùy tính phaûi tuaân thuû caùc quy luaät veà phoái caûnh… nhaèm giuùp ngöôøi xem coù aán töôïng hình aûnh gaàn ñuùng trong thöïc teá.
Moâ hình khung daây(Wireframe) duøng bieãu dieãn caùc ñoái töôïng 3D ñôn giaûn nhö caùc khoái ña dieän, caùc maët maø coù theå ñôn giaûn hoùa caùch theå hieän noù nhö goàm taäp hôïp goàm caùc ñænh vaø caùc caïnh noái lieàn caùc ñænh ñoù. Ñeå löu tröõ moâ hình khung daây caàn phaûi coù 2 danh saùch:
+ Danh saùch ñænh chöùa toïa ñoä caùc ñænh.
+ Danh saùch caïnh chöùa caùc caëp ñænh noái caïnh ñoù.
Caáu truùc döõ lieäu moâ taû Wireframe
Typedef struct
{
int NumVerts;
int NumEdges;
Point3D vert [ ];
Point3D edge[ ][2];
} wireframe;
Ñeå veõ caùc ñoái töôïng bieåu dieãn baèng moâ hình khung daây chuùng ta chæ caàn veõ caùc caïnh trong danh saùch caïnh. Tuy nhieân do caùc ñænh vaø caïnh ñöôïc ñònh nghóa trong 3D neân ñeå veõ ta phaûi chieáu leân maët phaúng 2D baèng caùc pheùp chieáu thích hôïp :
+Chieáu moãi ñieåm leân 2D.
+Veõ ñoaïn thaúng giöõa hai ñieåm chieáu naøy.
Giaûi thuaät:
+Khôûi taïo danh saùch ñænh.
Ñöa caùc ñænh ña giaùc vaøo danh saùch ñænh.
+Khôûi taïo danh saùch caùc caïnh.
Ñöa caùc caëp ñænh noái caïnh vaøo danh saùch caïnh.
+Khôûi taïo pheùp chieáu.
Tìm caùc ñieåm chieáu cuûa caùc ñænh wireframe.
+Veõ caùc caïnh cuûa ñoái töôïng.
Trong chöông trình minh hoïa, chuùng ta seõ duøng moâ hình wireframe ñeå bieåu dieãn moät soá ñoái töôïng ba chieàu ñaëc bieät nhö hình laêng truï, hình choùp.
¨ Hình laêng truï: Cô sôû cuûa hình laêng truï laø moät ña giaùc P naèm treân maët xy vaø ñöôïc queùt doïc theo truïc z ñeán moät chieàu cao H naøo ñoù. Neáu ña giaùc P coù n ñænh, hình laêng truï coù 2*n ñænh vaø 3*n caïnh.
Danh saùch ñænh: n ñænh ñaàu tieân daønh cho ña giaùc P coù toïa ñoä z baèng 0, n ñænh keá tieáp coù toïa ñoä z laø h.
Danh saùch caïnh: n caïnh ñöôïc choïn ñaàu tieân thuoäc ña giaùc P sao cho prism.edge[i,1] laø i vaø prism.edge[i,2] laø i+1 (ngoaïi tröø khi i =n thì seõ laø 1 ñeå thaønh ña giaùc), töông töï n caïnh keá ôû maët treân cuûa hình truï. Cuoái cuøng laø n caïnh ñöùng cuûa hình truï coù prism.edge[i+2n,1] laø i vaø prism.edge[i+2n] laø i+n.
¨ Hình choùp: Ñaùy cuûa hình choùp laø ña giaùc P coù n ñænh naèm treân maët xy. Vaø ñænh hình choùp khoâng thuoäc maët xy. Hình choùp coù 2*n ñænh vaø 2*n caïnh.
Danh saùch ñænh: n ñænh ñaàu tieân daønh cho ña giaùc P coù toïa ñoä z baèng 0, ñænh keá tieáp (n+1) coù toïa ñoä z laø h.
Danh saùch caïnh: n caïnh ñöôïc choïn ñaàu tieân thuoäc ña giaùc P sao cho pyramide.edge[i,1] laø i vaø pyramide.edge[i,2] laø i+1 (ngoaïi tröø khi i =n thì seõ laø 1 ñeå thaønh ña giaùc). n caïnh keá coù pyramide.edge[i+n,1] laø i vaø pyramide.edge[i+n,2] laø n+1.
3- Quan saùt vaät theå 3D qua heä toïa ñoä quan saùt
Cô sôû toaùn hoïc:
Moät ñoái töôïng 3-D ñöôïc xaùc ñònh bôûi caùc toïa ñoä x,y,z,nhöng maøn hình thì ñoái töôïng ñöôïc bieåu dieãn chæ vôùi caùc toïa ñoä x vaø y. Ñeå coù theå bieåu dieãn ñöôïc moät ñoái töôïng 3-D leân maøn hình, coù hai phöông phaùp ñeå thöïc hieän vaán ñeà treân laø pheùp chieáu song song vaø pheùp chieáu phoái caûnh.
Pheùp chieáu song song:
Loaïi hình ñôn giaûn nhaát cuûa pheùp chieáu song song laø pheùp chieáu tröïc giao nhöng laïi coù raát nhieàu öùng duïng trong caùc baûn veõ kyõ thuaät. Vôùi pheùp chieáu song song, moät ñoái töôïng 3-D ñöôïc theå hieän leân maøn hình baèng caùch boû qua caùc toïa ñoä z. Keát quaû laø moät hình 2-D ñôn giaõn. Nhö vaäy, vôùi tröôøng hôïp khoái vuoâng, hình aûnh theå hieän treân maøn hình chæ laø moät hình vuoâng.
b. Pheùp chieáu phoái caûnh:
Khaùc vôùi pheùp chieáu song song, pheùp chieáu phoái caûnh ñöôïc hình thaønh töø caùc tia chieáu khoâng song song vôùi nhau maø hoäi tuï taïi moät ñieåm goïi laø taâm chieáu. Kích thöôùc cuûa vaät qua pheùp chieáu seõ ñöôïc phoùng to hay thu nhoû phuï thuoäc vaøo khoaûng caùch giöõa taâm chieáu vaø maët phaúng chieáu (maët quan saùt). Khoaûng caùch giöõa maét vaø maët quan saùt goïi laø taàm nhìn.
0
P
x
z’
y’
x,
y
z
P’
D
R
Trong ñoù:
Ox’y’z’: Heä truïc toïa ñoä quan saùt.
D: Khoaûng caùch giöõa maët phaúng chieáu vaø heä truïc quan saùt.
R: Khoaûng caùch giöõa 2 goác toïa ñoä.
q: goùc giöõa hình chieáu OO’treân maët phaúng xoy vaø truïc ox.
j: goùc giöõa OO’vaø maët phaúng xoy.
Maét ñaët taïi goác heä toïa ñoä quan saùt ñaët doïc vôùi truïc O’z’höôùng vaøo goác O.
Maët phaúng quan saùt vuoâng goùc vôùi OO’.
Khi thay ñoåi goùc q vaø goùc j seõ daãn ñeán vieäc thay ñoåi goùc quan saùt vaät theå töø ñoù vieäc theå hieän ñoái töôïng ñöôïc quan saùt seõ linh ñoäng hôn.
Ñeå chuyeån ñoåi ñieåm P(x,y,z) trong heä toïa ñoä Oxyz ra toïa ñoä (xo,yo,zo) trong heä toïa ñoä thöù hai döïa treân x,y,z chuùng ta söû duïng coâng thöùc sau:
(xo,yo,zo,1) = (x,y,z,1) * T vôùi laø ma traän bieán hình T
-sinq -cosq sinj -cosqcosj 0
cosq -sinq sinj -sinqcosj 0
0 cosj -sinj 0
0 0 R 1
T =
vaø
xo = -x sinq + y cosq
yo = -x cosqsinj - y sinqsinj + z cosj
zo = -x cosqcosj - y sinqcosj - zsinj + R
Hình chieáu P’(xc, yc) cuûa ñieåm P(xo, yo, zo): Do maët phaúng maøn hình vuoâng goùc vôùi truïc Oz’ vaø taâm chieáu laø O’.
maøn hình
P
P’
yc
maøn hình
D
P
P’
z0
xc
x0
z’
y’
z’
x’
Aùp duïng tính chaát tam giaùc ñoàng daïng, ta coù:
xc = D*xo / zo
yc = D*yo / zo
Vôùi pheùp chieáu phoái caûnh, toïa ñoä cuûa ñieåm chieáu laø:
P’.xc =D*xo/ zo
P’.yc = D*yo/ zo
Vôùi pheùp chieáu song song, maét ñaët ôû voâ cöïc, vì vaäy:
xc = xo vaø yc = yo
Vaäy töø ñieåm P(x,y,z) treân ñoái töôïng 3D qua pheùp chieáu phoái caûnh hay song song ñaõ cho ta ñieåm P’(xc,yc) trong maët phaúng 2D.
+ Taêng goùc q seõ laøm heä quan saùt xeâ dòch trong maët phaúng xy theo chieàu ngöôïc chieàu kim ñoàng hoà laøm quay vaät theå theo chieàu kim ñoàng hoà.
+ Giaûm goùc q laøm quay vaät theå ngöôïc chieàu kim ñoàng hoà.
+ Taêng goùc j seõ ñaåy heä quan saùt leân treân laøm quay vaät xuoáng döôùi.
+ Giaûm goùc j laøm quay vaät leân treân.
Giaûi thuaät öùng duïng trong veõ moâ hình khung daây.
+ Tröôøng hôïp nhaán phím muõi teân
Up : goùc q = q - 5; (tính theo ñoä)
Down : goùc q = q + 5;
Left : goùc j = j - 5;
Right : goùc j = j + 5;
+ Khôûi taïo laïi pheùp chieáu
Tìm caùc ñieåm chieáu cuûa caùc ñænh wireframe.
+ Veõ laïi caùc caïnh cuûa ñoái töôïng.
4 -Kieåm tra quan heä Ñieåm - Ñöôøng thaúng
Cô sôû toaùn hoïc vaø giaûi thuaät:
Begin
- Nhaäp toïa ñoä 2 ñieåm A(x a, ya , za), B(xb, yb, zb ) maø ñöôøng thaúng d ñi qua.
- Nhaäp toïa ñoä ñieåm C (xc , yc , zc).
- Tính toïa ñoä vector chæ phöông cuûa ñöôøng thaúng d
. Vector AB = (xb - x a ; yb - ya ; zb -za ) ( hay AB=( a1,a2,a3 ) )
. Phöông trình toång quaùt ñöôøng thaúng d qua hai ñieåm A, B laø heä phöông trình töông ñöông vôùi heä sau:
a2x - a1y + 0 + a1ya - a2xa = 0
a3x + 0 - a1z + a1za - a3xa = 0
- Thay toïa ñoä cuûa ñieåm C (xc , yc , zc) vaøo heä phöông trình toång quaùt cuûa ñöôøng thaúng, ta ñöôïc:
a2xc - a1yc + 0 + a1ya - a2xa = 0
a3xc + 0 - a1zc + a1za - a3xa = 0
. Neáu heä treân thoûa thì ñieåm thuoäc ñöôøng thaúng, xuaát thoâng ñieäp “ÑIEÅM THUOÄC ÑÖÔØNG THAÚNG“;
. Neáu khoâng thoûa tính khoaûng caùch töø ñieåm ñeán ñöôøng thaúng:
.. Vieát phöông trình cuûa maët phaúng qua C(xc , yc , zc) vuoâng goùc vôùi ñöôøng thaúng d qua 2 ñieåm A , B vaø coù vector chæ phöông AB = (a1 , a2 , a3). Phöông trình maët phaúng coù daïng:
a1x + a2y + a3z - a1xc - a2yc - a3zc = 0 (* )
.. Vieát phöông trình tham soá cuûa ñöôøng thaúng qua A, B
X = a1t + xa
Y = a2t + ya
Z = a3t + za
.. Thay X , Y, Z vaøo phöông trình maët phaúng (*), ta ñöôïc:
a1( a1t + xa)+ a2( a2t + ya) + a3( a3t + za)
- a1xc - a2yc - a3zc = 0
t = a1xa - a2ya - a3za + a1xc + a2yc + a3zc /
( a12 + a22 + a32 )
.. Thay t vaøo phöông trình tham soá cuûa ñöôøng thaúng d qua A, B tìm ñöôïc ñieåm H
- Toïa ñoä cuaû ñieåm caét H(Xh , Yh ,Zh):
Xh = a1(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a12 + a22 + a32 ) + xa
Yh = a2(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a12 + a22 + a32 ) + ya
Zh = a3(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a12 + a22 + a32 ) + za
- Tính khoaûng caùch töø ñieåm C ñeán ñöôøng d qua 2 ñieåm A, B:
dch = | CH | = sqrt(( xc - xh )2 + ( yc - yh )2 + ( zc - za )2 )
- Xuaát toïa ñoä ñieåm H(Xh , Yh ,Zh) vaø khoaûng caùch dch
End.
5 - Kieåm tra quan heä Ñieåm - Maët phaúng
Cô sôû toaùn hoïc vaø giaûi thuaät:
Begin
- Nhaäp toïa ñoä 3 ñieåm A(x a , ya , za), B(xb , yb , zb ), C ( xc , yc , zc) xaùc ñònh maët phaúng mp(ABC) (3 ñieåm A, B, C khoâng thaúng haøng).
- Nhaäp toïa ñoä ñieåm D(xd , yd , zd).
- Tính caùc vector :
vector AB = ( xb - xa , yb - ya , zb - za )
vector AC = ( xc - xa , yc - ya , zc - za )
vector AD = ( xd - xa , yd - ya , zd - za )
- Xeùt ñieåm D(xd , yd, zd) coù thuoäc mp(ABC) khoâng?
. Tính tích höõu höôùng cuûa 2 vector AB, AC laø n = AB x AC coù daïng ñònh thöùc nhö sau:
yb - ya zb -za zb -za xb - xa xb - xa yb - ya
yc - ya zc -za , zc -za xc - xa , xc - xa yc - ya
n =
Hoaëc coù theå theo caùch vieát döôùi ñaây:
AB x AC = ((yb - ya )*(zc - za) - (yc - ya)*(zb - za),
(zb - za )*(xc - xa) - (zc - za)*(xb - xa),
(xb - xa )*(yc - ya) - (xc - xa)*(yb - ya))
. Tính tích voâ höôùng cuûa 2 veùc tô n=(AB x AC) vaø vector AD laø (ABxAC).AD baèng duøng ñònh thöùc caáp 3 vôùi ba veùc tô AB, AC, AD nhö sau:
xb - xa yb - ya zb - za
xc - xa yc - ya zc - za
xd - xa yd - ya zd - za
Dt =
Dt = (AB x AC).AD
= ( xd - xa )(( yb - ya )*( zc -za ) - (yc - ya )*( zb -za ) )
+ (yd - ya )(( zb -za )* (xc - xa ) - ( zc -za ) *(xb - xa ) )
+ (zd - za )((xb - xa )*( yc - ya ) - (xc - xa )*( yb - ya ))
. Ta xeùt ñònh thöùc caáp 3 naøy
.. Neáu Dt = 0 xuaát “Ñieåm D thuoäc mp(ABC)“
.. Neáu Dt 0 xuaát “Ñieåm D khoâng thuoäc mp(ABC)”
.. Neáu Dt 0 tìm khoaûng caùch töø ñieåm D ñeán mp(ABC)
Vieát phöông trình toång quaùt cuûa mp(ABC), coù 2 vector
AB = (xb - x a ,yb - ya , zb -za )
AC = (zb - za , yc - ya , zc - za )
N = (AB x AC) = (( yb - ya )*( zc - za ) - (yc - ya )*(zb - za ),
( zb - za )* (xc - xa ) - (zc - za )*(xb - xa ),
( xb - xa )*(yc - ya ) - (xc - xa )*(yb - ya ))
Neáu chuùng ta ñaët:
A = (yb - ya )*( zc -za ) - (yc - ya )*( zb -za )
B = ( zb -za )* (xc - xa ) - ( zc -za )*(xb - xa )
C = (xb - xa )*(ya - yb ) - (xc - xa )*( xb - xa)
D = -xaA - yaB - zaC .
vector n coù theå vieát laïi n =(A, B, C ) laø phaùp vector cuûa mp(ABC).
Vaø phöông trình toång quaùt cuûa maët phaúng mp(ABC) la:ø
Ax + By + Cz + D = 0
. Khoaûng caùch töø D(xd , yd , zd) ñeán mp(ABC)
ddmp(ABC) = abs( Axd + Byd + Czd + D ) / sqrt (A2 + B2 + C2 ) .
. Xuaát ra “ ddmp(ABC) “
- Tìm giao ñieåm cuûa ñöôøng thaúng d qua D(xd, yd, zd) vaø vuoâng goùc vôùi mp(ABC), coù vector chæ phöông laø phaùp vector n = (A, B, C). Phöông trình tham soá cuûa ñöôøng thaúng d:
X = At + xd
Y = Bt + yd
Z = Ct + zd
. Thay X , Y , Z vaøo phöông trình maët phaúng mp(ABC):
A( At + xa) + B( Bt + ya) + C(Ct + za) + D = 0
t = -(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )
. Thay t vaøo phöông trình tham soá cuûa ñöôøng thaúng d. Ta coù toïa ñoä ñieåm caét H(Xh , Yh ,Zh)
Xh = A(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 ))+ xd
Yh = B(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + yd
Zh = C(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + za
. Xuaát toïa ñoä ñieåm H(Xh , Yh ,Zh)
End.
6 - Kieåm tra quan heä Ñöôøng thaúng - Ñöôøng thaúng
Cô sôû toaùn hoïc vaø thuaät giaûi:
Begin
- Nhaäp toïa ñoä 2 ñieåm A(xa , ya , za) vaø B(xb , yb , zb) maø ñöôøng thaúng d ñi qua.
- Nhaäp toïa ñoä 2 ñieåm C(xc , yc , zc) vaø D(xd , yd , zd) maø ñöôøng thaúng d’ ñi qua.
- Tính veùc tô chæ phöông AB cuûa ñöôøng thaúng d:
AB =( xb - xa , yb - ya , zb - za )
( hay coù theå vieát goïn hôn AB = ( a1 , a2 , a3 ) )
- Tính veùc tô chæ phöông CD cuûa ñöôøng thaúng d’
CD = ( xd - xc , yd - yc , zd - zc )
(hay coù theå vieát goïn hôn CD = ( b1 , b2 , b3 ) )
- Vieát phöông trình cuûa ñöôøng thaúng d:
Phöông trình chính taéc:
( x - xa )/ a1 = ( y - ya )/ a2 = ( z - za )/ a3
Heä phöông trình toång quaùt cuûa ñöôøng thaúng d :
a2x - a1y + 0 + a1ya - a2xa = 0
a3x + 0 - a1z + a1za - a3xa = 0
- Vieát phöông trình cuûa ñöôøng thaúng d’:
Phöông trình chính taéc:
( x - xc )/ b1 = ( y - yc )/ b2 = ( z - zc )/ b3
Heä phöông trình toång quaùt cuûa ñöôøng thaúng d’:
b2x - b1y + 0 + b1yc - b2xc = 0
b3x + 0 - b1z + b1zc - b3xc = 0
- Xeùt söï töông quan cuûa ñöôøng thaúng d qua A, B vaø d’qua C, D:
· Ta coù 3 vector AB, CD, AC:
Vector AB = ( xb - xa , yb - ya , zb - za )
Vector CD = ( xd - xc , yd - yc , zd - zc )
Vector AC = ( xc - xa , yc - ya , zc - za )
· Laäp ñònh thöùc caáp 3 cuûa 3 vector AB, CD, AC
xb - xa yb - ya zb - za
xd - xc yd - yc zd - zc
xc - xa yc - ya zc - za
Dt =
Dt = (Ab x CD).AC
= ( xc - xa )(( yb - ya )*( zd - zc ) - ( yd - yc )*( zb -za ))
+ ( yc - ya )(( zd - zc )*( xc - xa ) - ( zc - za )*( xb - xa ))
+ ( zc - za )(( xb - xa )*( yd - yc ) - ( xd - xc )*( yb - ya ))
- Neáu (Dt0), xuaát ra keát quaû “Hai ñöôøng thaúng d vaø d’ cheùo nhau“.
- Neáu ((Dt = 0) AND (a1 / b1 = a2 / b2 = a3 / b3)), xuaát ra keát quaû “ Hai ñöôøng thaúng d vaø d’ song song“.
- Neáu ((Dt = 0) AND (a1 / b1 = a2 / b2 = a3 / b3) AND (d, d’coù 2 ñieåm chung)), xuaát ra keát quaû “ Hai ñöôøng thaúng d vaø d’ truøng nhau“.
- Neáu ((Dt = 0) AND (a1 / b1 a2 / b2 a3 / b3)), xuaát ra keát quaû “Hai ñöøông thaúng d vaø d’caét nhau“.
- Tìm toïa ñoä cuûa ñieåm caét nhau giöõa hai ñöôøng thaúng d vaø d’:
· Heä phöông trình toång quaùt cuûa ñöôøng thaúng d:
a2x - a1y + 0 + a1ya - a2xa = 0
a3x + 0 - a1z + a1za - a3xa = 0
· Heä phöông trình toång quaùt cuûa ñöôøng thaúng d’:
b2x - b1y + 0 + b1yc - b2xc = 0
b3x + 0 - b1z + b1zc - b3xc = 0
· Giaûi caùc heä phöông trình toång quaùt cuûa ñöôøng thaúng d, d’:
a2x - a1y + 0 + a1ya - a2xa = 0
a3x + 0 - a1z + a1za - a3xa = 0 (*)
b2x - b1y + 0 + b1yc - b2xc = 0
Ñaët:
d1 = a1ya - a2xa
d2 = a1za - a3xa
d3 = b1yc - b2xc
· Heä phöông trình (*) vieát laïi nhö sau:
a2x - a1y + 0 + d1 = 0
a3x + 0 - a1z + d2 = 0
b2x - b1y + 0 + d3 = 0
· Laäp ñònh thöùc caáp 3 cho heä ba phöông trình treân ñeå tìm toïa ñoä giao ñieåm cuûa ñöôøng thaúng d vaø d’:
a2 -a1 0
a3 0 -a1
b2 -b1 0
-d1 -a1 0
-d2 0 -a1
-d3 -b1 0
a2 -d1 0
a3 -d2 -a1
b2 -d3 0
Dt =
Dt =
Dt =
Dt =
a2 -a1 -d1
a3 0 -d2
b2 -b1 -d3
· Toïa ñoä giao ñieåm cuûa ñöôøng thaúng d, d’ laø E(xgd , ygd , zgd):
xgd = Dtxgd / Dtgd
ygd = Dtygd / Dtgd
zgd = Dtzgd / Dtgd
- Xuaát ra keát quaû toïa ñoä giao ñieåm E(xgd , ygd , zgd).
- Neáu (Dt 0) thì hai ñöôøng thaúng d vaø d’ cheùo nhau
· Tính khoaûng caùch giöõa ñöôøng thaúng d vaø d’(ñoaïn vuoâng goùc chung).
End.
7 - Kieåm tra quan heä Ñöôøng thaúng - Maët phaúng
Cô sôû toaùn hoïc vaø giaûi thuaät:
Begin
- Nhaäp toïa ñoä 3 ñieåm A(x a , ya , za), B(xb , yb , zb ), C(xc , yc , zc) xaùc ñònh maët phaúng mp(ABC) (3 ñieåm A, B, C khoâng thaúng haøng vôùi nhau).
- Nhaäp toïa ñoä 2 ñieåm E(xe , ye , ze) vaø F(xf , yf , zf) maø ñöôøng thaúng d ñi qua.
- Tính toïa ñoä caùc vector :
AB = ( xb - xa , yb - ya , zb - za )
AC = ( xc - xa , yc - ya , zc - za )
- Tính tích höõu höôùng cuûa 2 vector AB, AC coù daïng ñònh thöùc caáp 2 nhö sau (n = AB x AC chính laø phaùp vector cuûa mp(ABC))
yb -ya zb -za zb -za xb -xa xb -xa yb -ya
yc -ya zc -za , zc -za xc -xa , xc -xa yc -ya
Ab x AC =
Hoaëc coù theå vieát döôùi daïng nhö sau:
n = AB x AC = (( yb - ya )*( zc - za ) - ( yc - ya )*( zb -za ),
( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ),
( xb - xa )*( yc - ya ) - ( xc - xa)*( yb - ya ))
Neáu chuùng ta ñaët:
A = ( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za )
B = ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa )
C = ( xb - xa )*( ya - yb ) - ( xc - xa)*( xb - xa )
D = -xaA - yaB - zaC
Phöông trình toång quaùt cuûa maët phaúng mp(ABC) coù daïng:
Ax + By + Cz + D = 0
- Tính vector chæ phöông EF cuûa ñöôøng thaúng d ñi qua hai ñieåm E vaø F:
vector EF = ( xf - xe , yf - ye , zf - ze )
( coù theå vieát goïn laïi EF = ( a1 , a2 , a3 ) )
-Vieát phöông trình tham soá cuûa ñöôøng thaúng d:
X = a1t + xe
Y = a2t + ye
Z = a3t + ze
- Xeùt söï töông quan giöõa ñöôøng thaúng d qua 2 ñieåm E, F vaø mp(ABC) qua 3 ñieåm A, B, C :
· Tính tích voâ höôùng cuûa 2 vector (AB x AC) vaø vector EF baèng vieäc söû duïng ñònh thöùc caáp 3 vôùi ba vector AB, AC, EF nhö sau:
vector AB = ( xb - xa , yb - ya , zb - za )
vector AC = ( xc - xa , yc - ya , zc - za )
vector EF = ( xf - xe , yf - ye , zf - ze )
Ñònh thöùc caáp 3:
xb - xa yb - ya zb - za
xc - xa yc - ya zc - za
xf - xe yf - ye zf - ze
Dt =
Dt = (AB x AC).EF
= ( xf - xe )(( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ))
+ ( yf - ye )(( zb - za )*( xc - xa ) - ( zc -za )*( xb - xa ))
+ ( zf - ze )(( xb - xa )*( yc - ya ) - ( xc - xa)*( yb - ya ))
· Xeùt ñònh thöùc caáp 3 naøy:
+ Neáu Dt = 0, xuaát ra keát quaû “Ñöôøng thaúng d song song hoaëc chöùa trong mp(ABC)“
+ Neáu Dt0, xuaát ra keát quaû “Ñöôøng thaúng d caét mp(ABC)“
- Neáu Dt0, tìm toïa ñoä giao ñieåm giöõa ñöôøng thaúng d vaø mp(ABC):
+ Phöông trình toång quaùt cuûa maët phaúng mp(ABC) coù daïng:
Ax + By + Cz + D = 0
+ Phöông trình tham soá cuaû ñöôøng thaúng d:
X = a1t + xe
Y = a2t + ye
Z = a3t + ze
+ Thay X, Y, Z vaøo phöông trình maët phaúng (ABC), ta ñöôïc:
A( a1t + xe) + B( a2t + ye) + C(a3t + ze) + D = 0
t = -(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 )
+ Thay t vaøo phöông trình tham soá cuaû ñöôøng thaúng d, ta coù toïa ñoä giao ñieåm cuûa d vaø mp(ABC):
Xgd = a1(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + xe
Ygd = a2(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + ye
Zgd = a3(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + ze
+ Xuaát ra toïa ñoä giao ñieåm H(xgd , ygd , zgd).
- Tính goùc giöõa ñöôøng thaúng d qua E, F vaø mp(ABC) qua A, B, C
Cos(AB^n) = abs(Aa1 + Ba2 + Ca3 ) / sqrt(A2 + B2 + C2) * sqrt(a12 + a22 + a32)
- Ñöôøng thaúng d song song vôùi mp(ABC). Tính khoaûng caùch töø ñöôøng thaúng d ñeán mp(ABC):
+ Vieát phöông trình ñöôøng thaúng d’qua ñieåm E vaø vuoâng goùc vôùi maët phaúng (ABC) coù phaùp vector n=(A , B, C )
X = At + xe
Y = Bt + ye
Z = Ct + ze
+ Thay X , Y , Z vaøo phöông trình maët phaúng (ABC), ta ñöôïc:
A( At + xe) + B( Bt + ye) + C(Ct + ze) + D = 0
t = -(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 )
+ Thay t vaøo phöông trình tham soá cuûa ñöôøng d’, ta coù toïa ñoä giao ñieåm giöõa ñöôøng thaúng d’vaø mp(ABC):
Xh = A(-(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 )) + xe
Yh = B(-(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 )) + ye
Zh = C(-(Axe + Bye + Cze + D ) / ( A2 + B2 + C2 ) ) + ze
+ Xuaát ra toïa ñoä giao ñieåm H( xh , yh , zh ) .
+ Tính khoaûng caùch töø ñöôøng thaúng d ñeán mp(ABC), chính laø ñoaïn AH:
dah = sqrt ( ( xh - xa )2 + ( yh - ya )2 + ( zh - za )2 )
+ Xuaát ra khoaûng caùch dah
End.
8 . Kieåm tra quan heä Maët phaúng - Maët phaúng
Cô sôû toaùn hoïc vaø thuaät giaûi:
Begin
- Nhaäp toïa ñoä 3 ñieåm A(x a, ya, za), B(xb, yb, zb ), C(xc, yc, zc) ñeå xaùc ñònh toïa ñoä mp(ABC)
- Nhaäp toïa ñoä 3 ñieåm M(x m , ym , zm), P(xp , yp , zp ), Q( xq , yq , zq) ñeå xaùc ñònh toïa ñoä maët phaúng mp(MPQ).
- Tính toïa ñoä caùc veùc tô cuûa mp( ABC)
vector AB = ( xb - xa , yb - ya , zb - za )
vector AC = ( xc - xa , yc - ya , zc - za )
(3 ñieåm A,B,C taïo thaønh mp(ABC) neân vector AB khoâng cuøng phöông vôùi vectô AC)
-Tính tích höõu höôùng cuûa 2 vector AB, AC laø n = (AB x AC),n chính laø phaùp vector cuûa mp(ABC) coù toïa ñoä :
n = AB x AC = (( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ),
( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ),
( xb - xa )*( yc - ya ) - ( xc - xa )*( yb - ya ))
Neáu chuùng ta ñaët:
A = ( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za )
B = ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa )
C = ( xb - xa )*( ya - yb ) - ( xc - xa )*( xb - xa)
D = -xaA - yaB - zaC .
Phöông trình toång quaùt cuûa maët phaúng mp(ABC) coù daïng:
Ax + By + Cz + D = 0
- Tính toïa ñoä caùc vector cuûa maët phaúng mp(MPQ) :
vector MP = ( xp - xm , yp - ym , zp - zm )
vector MQ = (xq - xm , yq - ym , zq - zm )
(3 ñieåm M, P, Q taïo thaønh mp(MPQ) neân vector MP khoâng cuøng phöông vôùi vector MQ)
- Tính tích höõu höôùng cuûa 2 vector MP, MQ laø m = MP x MQ, m chính laø phaùp vector cuûa mp(MPQ), coù toïa ñoä :
m = MP x MQ
yp -ym zp -zm zp -zm xp -xm xp - xm yp - ym
yq -ym zq -zm , zq -zm xq -xm , xq - xm yq - ym
m =
hay coù theå vieát nhö sau:
m = MP x MQ = (( yp - ym )*( zq -zm ) - (yq - ym )*( zp -zm ),
( zp -zm )* (xq - xm ) - ( zq -zm ) *(xp - xm ),
(xp - xm )*( yq - ym ) - (xq - xm )*( yp - ym ))
Neáu chuùng ta ñaët:
A1 = (yp - ym )*( zq -zm ) - (yq - ym )*( zp -zm )
B1 = ( zp -zm )* (xq - xm ) - ( zq -zm ) *(xp - xm )
C1 = (xp - xm )*(yp - ym ) - (xq - xm )*( xp - xm)
D1 = -xmA1 - ymB1 - zmC1 .
Phöông trình toång quaùt cuûa maët phaúng mp(MPQ):
mp(MPQ) = A1x + B1y + C1z + D1 = 0
- Xeùt söï töông quan cuûa 2 maët phaúng treân:
· Neáu (A/A1 = B/B1 = C/C1) xuaát ra keát quaû “Hai maët phaúng truøng nhau“.
· Neáu (A/A1 = B/B1 = C/C1 D/D1) xuaát ra keát quaû “Hai maët phaúng song song vôùi nhau“.
· Neáu (A/A1 B/B1) hoaëc (B/B1 C/C1) hoaëc (A/A1 C/C1) xuaát ra keát quaû “Hai maët phaúng caét nhau“.
- Hai maët phaúng mp(ABC) vaø mp(MPQ) caét nhau theo moät giao tuyeán laø ñöôøng thaúng coù phöông trình laø heä phöông trình cuûa hai maët phaúng mp(ABC) vaø mp(MPQ):
Ax + By + Cz + D = 0
A1x + B1y + C1z + D1 = 0
- Tính toïa ñoä giao ñieåm thuoäc giao tuyeán:
· Neáu (A/A1 B/B1) thì toïa ñoä z coù theå ñöôïc choïn tuyø yù cho ñôn giaûn, duøng ñònh thöùc caáp 2 tìm toïa ñoä giao tuyeán :
Ax + By + Cz + D = 0
A1x + B1y + C1z + D1 = 0
Ta tính ñöôïc:
Dx1 = AB2 - A1B
Dx1 = B1(-D - Ck1 ) + B( D1 + C1k1 )
Dy1 = A(-D1 – C1k1 ) + A1( D + C1k1 )
Suy ra:
X1 = Dx1/ D
Y1 = Dy1/ D
Z1= k1
Þ Toïa ñoä I(X1 , Y1 , Z1)
· Tìm toïa ñoä ñieåm thöù 2:
Dx2 = AB2 - A1B
Dx2 = B1(-D - Ck2 ) + B( D1 + C1k2 )
Dy2 = A(-D1 - C1k2 ) + A1( D + C1k2 )
X2 = Dx2 / D
Y2 = Dy2 / D
Z2 = k2
Þ Toïa ñoä J(X2 , Y2 , Z2)
· Xuaát toïa ñoä 2 ñieåm thuoäc giao tuyeán J(X2, Y2 , Z2 ) vaø I(X1, Y1, Z1)
- Neáu hai maët phaúng song song, tính khoaûng caùch cuûa 2 maët phaúng:
· Tìm giao ñieåm cuûa ñöôøng thaúng d qua ñieåm M( xm, ym, zm) vaø vuoâng goùc vôùi mp(ABC), coù vector chæ phöông laø phaùp vector cuûa mp(ABC) laø vector n=(A,B,C).
· Vieát phöông trình tham soá cuûa ñöôøng thaúng d:
X = At + xm
Y = Bt + ym
Z = Ct + zm
· Thay X, Y, Z vaøo phöông trình maët phaúng mp(ABC):
A( At + xm)+B( Bt + ym) + C(Ct + zm) + D = 0
t = -(Axm + Bym + Czm + D ) / ( A2 + B2 + C2 )
· Thay t vaøo phöông trình tham soá cuûa ñöôøngthaúng d:
+ Ta coù toïa ñoä ñieåm caét H(Xh , Yh, Zh):
Xh = A(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 ))+ xd
Yh = B(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + yd
Zh = C(-(Axd + Byd + Czd + D ) / ( A2 + B2 + C2 )) + zd
· Khoaûng caùch hai mp(ABC) vaø mp(MPQ) laø ñoaïn MH:
dmh =|MH | = sqrt ( ( xh - xm)2 + ( yh - ym )2 + ( zh - zm )2 )
· Xuaát khoaûng caùch dmh
End.
9-Kieåm tra tính ñoàng phaúng cuûa ña giaùc
Cô sôû toaùn hoïc:
Ña giaùc goïi laø phaúng neáu moïi ñænh cuûa noù naèm trong moät maët phaúng. Trong tröôøng hôïp naøy ba ñænh baát kyø (khoâng thaúng haøng), coù theå duøng ñeå xaùc ñònh maët phaúng chöùa noù. Khi coù hôn ba ñænh, coù theå caùc ñieåm khoâng cuøng naèm treân 1 maët phaúng. Vì vaäy caùc öùng duïng phaûi kieåm tra döõ lieäu ñeå baûo ñaûm tính ñoàng phaúng.
Choïn moät trong m ñieåm, goïi laø P1, laøm ñieåm choát (pivot) vaø hình thaønh (m-1) vector choát Vi=Pi-P1, vôùi i = 2,…, m. Caùc vector naøy naèm trong cuøng 1 maët phaúng neáu vaø chæ neáu caùc ñænh Pi naèm trong cuøng moät maët phaúng. Ta bieát ba vector ñoàng phaúng neáu vaø chæ neáu tích boä ba voâ höôùng cuûa chuùng trieät tieâu.Vì vaäy, taïo (m-3) tích boä ba voâ höôùng Vi.(V3.V2) vôùi i=4,…., m. Neáu moät trong caùc tích naøy khaùc zero ña giaùc seõ khoâng ñoàng phaúng.
Giaûi thuaät:
- Taïo danh saùch (n-1) vector töø ña giaùc P coù n caïnh
- Voøng laëp töø i =3 ñeán i =n-1
+Tính tích boä ba voâ höôùng S= Vi .(V1 x V2)
+ Neáu (S khaùc 0)
Return
Ña giaùc khoâng ñoàng phaúng.
- Return
Ña giaùc ñoàng phaúng
10 -Tính theå tích hình laêng truï:
Giaûi thuaät:
- Tính S laø dieän tích cuûa ña giaùc ñaùy.
- Nhaäp h, chieàu cao cuûa hình laêng truï.
- Tính theå tích ña giaùc V = S*h.
11- Tính theå tích hình choùp:
Giaûi thuaät:
- Tính S laø dieän tích cuûa ña giaùc ñaùy.
- Nhaäp h, chieàu cao cuûa hình choùp.
- Tính theå tích V= S*h /3.
12- Tính theå tích hình noùn:
Giaûi thuaät:
- Nhaäp R, baùn kính ñaùy hình noùn.
- Nhaäp h, chieàu cao hình noùn.
- Tính theå tích V = S*h / 3 = Pi*R2*h / 3.
PHAÀN III: THIEÁT KEÁ CHÖÔNG TRÌNH
I. THIEÁT KEÁ GIAO DIEÄN THÖÏC HIEÄN KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC
Thieát keá giao dieän cho quaù trình thöïc hieän nhöõng öùng duïng trong vieäc kieåm tra caùc quan heä hình hoïc, caäp nhaät caùc thoâng soá veà kích thöôùc vuøng cuûa vuøng Client:
Lôùp CMainFrame : Coù chöùc naêng taïo maøn hình vuøng Client.
Lôùp CApp : Coù chöùc naêng thöïc hieän öùng duïng kieåu ñôn taøi lieäu (SDI).
Lôùp CView : Coù chöùc naêng hieån thò nhöõng hieän thöïc cuaû chöông trình kieåm tra caùc quan heä hình hoïc.
Lôùp CDoc : Coù chöùc naêng xöû lyù vieäc löu tröõ döõ lieäu.
Lôùp CDialog : Coù chöùc naêng nhaäp, xuaát döõ kieän.
II. MOÄT SOÁ KIEÅU DÖÕ LIEÄU ÑÖÔÏC SÖÛ DUÏNG TRONG CHÖÔNG TRÌNH
Caùc ñænh cuûa ña giaùc P phaúng ñöôïc löu tröõ laàn löôït trong danh saùch kieåu CPoint nhö P[0].x, P[0].y; P[1].x,P[1].y; …. Vôùi ñænh cuoái ñöôïc nhaän bieát bôûi chæ soá ña giaùc keøm theo.
Kieåu döõ lieäu ñieåm trong khoâng gian ba chieàu (3D), ñöôïc khai baùo nhö sau:
typedef struct
{
long x;
long y;
long z;
} point3d ;
Caáu truùc döõ lieäu moâ taû Wireframe bao goàm:
+Danh saùch ñænh chöùa toïa ñoä caùc ñænh
+Danh saùch caïnh chöùa caùc caëp ñænh noái caïnh ñoù.
typedef struct
{
int NumV;
int NumE;
point3d vert[20];
int edge[30][2];
} Wireframe;
Kieåu döõ lieäu duøng ñeå taïo danh saùch caïnh töø caùc ñænh lieân tieáp nhau:
typedef struct
{
CPoint A;
CPoint B;
} TypeListEdge;
Kieåu döõ lieäu löu tröõ caùc ñieåm, coù keøm theo côø ñeå phaân bieät caùc loaïi ñieåm khaùc nhau (ñieåm giao nhau giöõa 2 ña giaùc, ñieåm naøy ñaõ ñöôïc duyeät hay chöa duyeät; hay ñænh cuûa ña giaùc) ñöôïc duøng trong thuû tuïc kieåm tra quan heä hai ña giaùc, ñöôïc khai baùo nhö sau:
typedef struct
{
CPoint P;
int CFlag;
} ListPoint;
III. CAÙCH TOÅ CHÖÙC CAÙC HAØM TRONG 2D
Caùc haøm ñöôïc giôùi thieäu döôùi ñaây ñöôïc nhoùm laïi thaønh töøng nhoùm giuùp cho vieäc theo doõi ñöôïc deã daøng hôn
Nhöõng haøm ñöôïc söû duïng trong lôùp CkiemTra2DView.cpp
Construction/destruction lôùp CView
CKiemTra2DView:: CKiemTra2DView()
CKiemTra2DView:: ~CKiemTra2DView()
Caùc haøm taïo cöûa soå, veõ cuûa lôùp CView
BOOL CKiemTra2DView::PreCreateWindow(CREATESTRUCT& cs)
void CKiemTra2DView:: OnDraw(CDC* pDC)// Debug
void CKiemTra2DView::AssertValid() const
void CKiemTra2DView::Dump(CDumpContext& dc) const
CTestHHDoc* CKiemTra2DView::GetDocument()
Caùc haøm phuïc vuï veõ trong 2D
void CKiemTra2DView::OnVediem()
void CKiemTra2DView::OnUpdateVediem(CCmdUI* pCmdUI)
void CKiemTra2DView::OnVeduongthang1()
void CKiemTra2DView::OnUpdateVeduongthang1(CCmdUI* pCmdUI)
void CKiemTra2DView::OnVeduongthang2()
void CKiemTra2DView::OnUpdateVeduongthang1(CCmdUI* pCmdUI)
void CKiemTra2DView:: OnVedagiac1()
void CKiemTra2DView::OnUpdateVedagiac1(CCmdUI* pCmdUI)
void CKiemTra2DView::OnVedagiac2()
void CKiemTra2DView::OnUpdateVedagiac2(CCmdUI* pCmdUI)
Caùc haøm lieân quan ñeán mouse
void CKiemTra2DView::OnLButtonDown(UINT nFlags, CPoint point)
void CKiemTra2DView::OnLButtonUp(UINT nFlags, CPoint point)
void CKiemTra2DView::OnRButtonDown(UINT nFlags, CPoint point)
void CKiemTra2DView::OnMouseMove(UINT nFlags, CPoint point)
Tính Max ,Min cuûa 2 giaù trò(thuû tuïc tìm giaù trò lôùn nhaát giöõa hai giaù trò)
int Max(int x, int y)
int Min(int x, int y)
{
int tam;
tam=(x>=y)? y:x;
return tam;
}
{
int tam;
tam=(x>=y)? x:y;
return tam;
}
Caùc haøm kieåm tra ñieåm P ôû beân trong / beân ngoaøi ña giaùc
BOOL TestPoint_Boundary (CPoint P,UINT n,CPoint dayP[])
BOOL Giaodiem(CPoint P,UINT n,CPoint dayP[])
void CKiemTra2DView::OnTestDiem()
Caùc haøm kieåm tra quan heä giöõa 2 ñöôøng thaúng
double LengthOfSegment(CPoint A,CPoint B)
void CKiemTra2DView::OnTinhgoc()
void CKiemTra2DView::OnHinhchieu()
UINT Intersect(CPoint A,CPoint B,CPoint C,CPoint D,CPoint &M)
Caùc haøm kieåm tra quan heä giöõa ñoaïn thaúng vaø ña giaùc
void Trungdiem(CPoint A,CPoint B,CPoint &TDiem)
void ClippingLine(CPoint A,CPoint B,UINT nDinh,CPoint DGiac[],
CPoint DsachDcat[],UINT &SoDcat)
void CKiemTra2DView::OnDoanthang_Dagiac()
Haøm kieåm tra Ña giaùc loài hay loõm?
long Toado(CPoint A, CPoint B)
void CKiemTra2DView:: OnTest2Dagiac()
Haøm tính dieän tích cuûa ña giaùc
void CKiemTra2DView::OnTinhdientich()
Nhoùm caùc haøm coù lieân quan tôùi pheùp chieáu song song vaø phoái caûnh
void InitProjection(double &t1,double &t2,double &t3,double &t4,double &t5,double &t6,double &t7,double &t8,float xRot,float yRot)
void Projection(BOOL PhepChieu ,float xRot,float yRot, Wireframe &WF)
void CKiemTra2DView:: OnChieuPhoiCanh()
void CKiemTra2DView::OnUpdateChieuPhoiCanh(CCmdUI* pCmdUI)
void CKiemTra2DView:: OnChieuSongSong()
void CKiemTra2DView::OnUpdateChieuSongSong(CCmdUI* pCmdUI)
Nhoùm haøm lieân quan ñeán caùc thao taùc cuûa hình laêng truï
void CKiemTra2DView:: OnLangTru()
void CKiemTra2DView::OnChieuLangTru()
void CKiemTra2DView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags)
Nhoùm haøm lieân quan ñeán caùc thao taùc cuûa hình choùp
void CKiemTra2DView::OnNhapDinhChop()
void CKiemTra2DView:: OnChieu_Chop()
Nhoùm haøm lieân quan ñeán caùc thao taùc cuûa hình noùn
void CKiemTra2DView::OnHinhnon()
void CKiemTra2DView::OnChieu_Non()
Caùc haøm kieåm tra tính ñoàng phaúng cuûa ña giaùc
void CKiemTra2DView::OnNhapDagiac()
void CKiemTra2DView::PlanarPolygon()
Toâ maøu ña giaùc
void CKiemTra2DView::OnTomaudagiac()
Kieåm tra quan heä giöõa 2 ña giaùc
void CKiemTra2DView::OnTest2Dagiac()
Nhöõng haøm ñöôïc söû duïng trong lôùp CKiemTra2DDoc.cpp
CkiemTra2DDoc::CkiemTra2DDoc()
CkiemTra2DDoc::~ CkiemTra2DDoc()
BOOL CkiemTra2DDoc::OnNewDocument()
void CkiemTra2DDoc::Serialize(CArchive& ar)
IV. CAÙCH TOÅ CHÖÙC CAÙC HAØM TRONG OPENGL 3D
Trong phaàn kieåm tra trong 3D, coù caùc phöông thuùc xöû lyù caùc thao taùc nhö sau:
Nhöõng haøm ñöôïc söû duïng trong lôùp CkiemTra3Dview
Construction/destruction lôùp CView
CKiemTra3DView::CKiemTra3DView() CKiemTra3DView::~CKiemTra3DView()
Caùc haøm taïo cöûa soå, veõ cuûa lôùp CView
BOOLCKiemTra3DView::PreCreateWindow(CREATESTRUCT& cs)
void CKiemTra3DView::OnDraw(CDC* pDC)
void CKiemTra3DView::AssertValid() const
void CKiemTra3DView::Dump(CDumpContext& dc) const
Haøm taïo ngöõ caûnh ñeå phuø hôïp vôùi vieäc veõ caùc vaät theå 3D
int CKiemTra3DView::OnCreate(LPCREATESTRUCT pCreateStruct)
Caùc haøm ñieàu chænh kích thöôùc, taïo maøu neàn
void CKiemTra3DView::OnDestroy()
void CKiemTra3DView::OnSize(UINT nType, int cx, int cy)
BOOL CKiemTra3DView::OnEraseBkgnd(CDC* pDC)
void CKiemTra3DView::GLResize(GLsizei w, GLsizei h)
void CKiemTra3DView::GLSetupRC()
void CKiemTra3DView::Khoitaopalette()
BOOL CKiemTra3DView::OnQueryNewPalette()
void CKiemTra3DView::OnPaletteChanged(CWnd* pFocusWnd)
Haøm nhaán caùc phím muõi teân ñeå quan saùt vaät theå
void CkiemTra3Dview::OnKeyDown(UINT nChar, UINT nRepCnt, INT Flags)
Caùc haøm thöïc hieän caùc thao taùc nhaäp toïa ñoä cho maët phaúng, ñieåm, ñöôøng thaúng
void CKiemTra3DView:: OnNhapMPhang1()
void CKiemTra3DView:: OnNhapMPhang2()
void CKiemTra3DView:: OnNhapTDDiem()
void CKiemTra3DView:: OnNhapTDDuong1()
void CKiemTra3DView:: OnNhapTDDuong2()
Caùc haøm thöïc hieän caùc thao taùc kieåm tra, tính toaùn giöõa caùc ñoái töôïng ñieåm, ñöôøng thaúng, maët phaúng.
void CKiemTra3DView:: OnKtraDiemMP()
void CKiemTra3DView:: OnVeGiao2MP()
void CKiemTra3DView:: OnKtraDiem_Duong()
void CKiemTra3DView:: OnKtra2DThang()
void CKiemTra3DView:: OnKtraDuong_MP()
void CKiemTra3DView:: OnTinhGoc2MP()
void CKiemTra3DView:: OnTinhGocDuong_MP()
void CKiemTra3DView:: OnTinhGoc2DT()
void CKiemTra3DView:: OnTinhKCDiem_Duong()
void CKiemTra3DView:: OnTinhKC2Duong()
void CKiemTra3DView:: OnTinhKC2MP()
void CKiemTra3DView:: OnDiemDongPhang()
void CKiemTra3DView:: Ve_Hai_MP()
void CKiemTra3DView:: On2MPhang()
void CKiemTra3DView:: GT_hai_mp1()
void CKiemTra3DView:: GT_hai_mp3()
void CKiemTra3DView:: OnVe_KC_Diem_MP()
void CKiemTra3DView:: OnTinh_KC_Diem_MP()
void CKiemTra3DView:: Ve_Diem_MP()
Caùc haøm thöïc hieän vieäc veõ, demo caùc vaät theå
void CKiemTra3DView:: GLRenderScene()
void CKiemTra3DView:: Cube()
void CKiemTra3DView:: HinhChop()
void CKiemTra3DView:: Wireframchop()
void CKiemTra3DView:: OnCube()
void CKiemTra3DView:: Onscence()
void CKiemTra3DView:: OnHinhchop()
void CkiemTra3Dview:: OnWireframWireframchop()
Haøm thöïc hieän thao taùc xoaù maøn hình
void CKiemTra3DView:: OnClearScreen()
Nhöõng haøm ñöôïc söû duïng trong lôùp CkiemTra3Ddoc
CkiemTra3DDoc:: CkiemTra3DDoc()
CkiemTra3DDoc:: ~ CkiemTra3DDoc()
BOOL CkiemTra3DDoc:: OnNewDocument()
void CkiemTra3DDoc:: Serialize(CArchive& ar)
PHAÀN IV: HÖÔÙNG DAÃN SÖÛ DUÏNG CHÖÔNG TRÌNH
Trong phaàn naøy, toâi seõ ñeà caäp caùch söû duïng caùc thao taùc cuûa vieäc kieåm tra caùc quan heä hình hoïc trong phaàn 2D vaø 3D.
I. Giao dieän phaàn 2D
Maøn hình giao dieän chính cuûa chöông trình, ngöôøi söû duïng coù theå xem caùc thoâng tin veà chöông trình vaø choïn thao taùc kieåm tra trong 2D vaø 3D.
Giao dieän bao goàm 4 thao taùc:
Kieåm tra 2D.
Kieåm tra 3D.
Ñeà taøi.
Thoaùt chöông trình.
Maøn hình laøm vieäc trong phaàn 2D, bao goàm caùc ñeà muïc nhö thao taùc trong 2D, thao taùc trong 3D vaø caùc thao taùc xöû lyù töông öùng. Ngöôøi söû duïng coù theå duøng phím Enter hay toå hôïp caùc phím ñeå choïn caùc thao taùc phuø hôïp. Trong phaàn kieåm tra 2D bao goàm caùc ñoái töôïng ñieåm, ñöôøng thaúng, ña giaùc vaø caùc thao taùc kieåm tra töông öùng vôùi caùc ñoái töôïng hình hoïc naøy.
Maøn hình laøm vieäc khi ngöôøi duøng choïn moät trong caùc thao taùc kieåm tra giöõa caùc ñoái töôïng hình hoïc
II. Giao dieän phaàn 3D
Trong phaàn 3D, toâi xin giôùi thieäu moät soá hình aûnh demo chöông trình
Kieåm tra ñieåm coù ñoàng phaúng vôùi maët phaúng hay khoâng?
Veõ vaät theå phuï thuoäc vaøo yeâu caàu ngöôøi duøng
III. Ñeà nghò höôùng phaùt trieån
Taïo theâm nhöõng chöùc naêng kích hoaït laïi nhöõng ñoái töôïng hình hoïc khi ñaõ ñöôïc theå hieän treân vuøng Client nhö:
Keùo giaûn kích thöôùc
Dòch chuyeån nhöõng ñoái töôïng tuyø yù
Caäp nhaät laïi döõ lieäu cho caùc vò trí môùi
Töø nhöõng töông quan cô baûn ñaõ ñöïôc thieát keá cuûa ñeà taøi naøy, xaây döïng leân nhieàu baøi toaùn hình hoïc khaùc.
TAØI LIEÄU THAM KHAÛO
¤
[1] Leâ Taán Huøng, Huyønh Quyeát Thaéng,
Kyõ thuaät ñoà hoïa,
Nhaø xuaát baûn Khoa Hoïc vaø Kyõ Thuaät 2000.
[2] Leâ Minh Trí,
Kyõ naêng laäp trình Windows baèng Visual C++ 6.0 (Taäp 1 vaø 2),
Các file đính kèm theo tài liệu này:
baocao.doc
BC-THAI1.ppt
Source.rar
