Tài liệu Thiết kế hệ thống kiểm tra các quan hệ hình học trong không gian 2d và 3d

Luaän vaên toát nghieäp 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 đánh giá lại quá trính học tập, nghiên cứu của tôi. Nên về mặt tinh thần tôi đã cố gắng tím hiểu, nghiên cứu, và chuẩn bị khá chu đáo cho việc thực hiện. Nhưng sự tiếp thu cũng có những giới hạn nhất định, bởi trong lĩnh vực máy tình cũng như cơ sở toán học rộng lớn, không gian diễn dịch có thể vô hạn, sự thực hiện một ý tưởng nào đó có thể trong toán học thực hiện được, nhưng việc thể hiện thuật toán bằng máy tình thí có những vấn đề khó thể thực hiện, ví vậy đề tài chắc chắn còn nhiều thiếu sót nhất định. Mong quý Thầy cô, Anh chị và các bạn thông cảm, đóng góp ý kiến giúp đỡ. Tôi thành thật cảm ơn …! SINH VIÊN THỰC HIỆN LÊ QUỐC THÁI PHẦN I: GIƠÙI THIỆU I. SƠ LƯỢC VỀ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 1 Luaän vaên toát nghieäp Để cho người đọc tham khảo đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“ dễ dàng hính dung được, tôi xin giới thiệu sơ lược về đề tài. Nhiệm vụ thực hiện của đề tài: Thiết kế hệ thống kiểm tra các quan hệ hính học trong:  Không gian hai chiều (2D)  Không gian ba chiều (3D) Với ngôn ngữ thể hiện trên môi trường Visual C++. Đề tài áp dụng các kiến thức về cơ sở toaùn học và không gian vector trong đồ họa máy tình, để xây dựng những thuật toán kiểm tra các quan hệ hính học. Để dễ dàng hơn tôi xin trính bày một vì dụ điển hính như sau: Ví duï: cho đường thẳng a qua hai điểm A và B và đường thẳng b qua hai điểm C và D trong không gian 2D hay 3D thí hai đường thẳng này cũng có những sự tương quan với nhau, như trùng nhau, cắt nhau với một góc nào đó, chéo nhau (trong không gian 3D), hay song song… Sau khi đưa vào những điều kiện giả thiết ban đầu (Input), thí chương trính thực hiện và đưa ra kết quả kiểm tra (output) của giả thiết trên là hai đường thẳng a và b đã tương quan như thế nào với nhau? Cắt nhau một góc bao nhiêu độ, song song, hay trùng nhau... Đó là về mặt thuật toán chương trính kiểm tra, đây chỉ mới là một tác vụ thực hiện của vấn đề này. Với bài toán như trên nếu chỉ đưa ra được những kết luận với những dòng thông điệp thí chúng ta thấy rằng đề tài trở nên quá đơn giản không phong phú và hấp dẫn qua ý kiến của người đọc hoặc tham khảo. Một tác vụ cùng đồng thời với bài toán trên mà nhiệm vụ của đề tài yêu cầu thực hiện là khi đưa vào giả thiết bài toán chẳng hạn hai điểm A và B với những tọa độ xác định nào đó, qua hai điểm này sẽ thực hiện vẽ lên một đoạn thẳng qua hai điểm A và B. Từ đó thấy vấn đề một cách trực quan hơn, hay vẽ ra góc giữa hai đường thẳng, chình với những thể hiện này đề tài trở nên hấp dẫn phong phú hơn, tất nhiên vấn đề này không ìt những khó khăn cho người thực hiện đề tài. Trong phần nội dung tôi sẽ trính bày chi tiết hơn về đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC TRONG 2D VÀ 3D“. II. GIỚI THIỆU SƠ LƯỢC NGÔN NGỮ THỂ HIỆN ĐỀ TÀI II.1. SƠ LƯỢC NGÔN NGỮ Ở phần I giới thiệu sơ lược về “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“, tôi đã trính bày một vì dụ về yêu cầu nhiệm vụ để thực hiện một tác vụ kiểm tra vấn đề nào đó của đề tài này. Để thực hiện những vấn đề đó tôi nghiên cứu và thực hiện trên môi trường ngôn ngữ Visual C++. Visual C++ là một phần mềm lập trính hướng đối tượng được phát triển trên cơ sở là ngôn ngữ lập trính C và C++. Ở đây tôi thể hiện đề tài trên ngôn ngữ Visual C++ bởi Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 2 Luaän vaên toát nghieäp lẽ hiện nay ngôn ngữ này được xem là một trong các ngôn ngữ hoã trợ (support user) mạnh và phổ biến nhất. Cùng mục đìch sâu xa hơn nữa là để cho những đề tài sau này có thể trên cùng ngôn ngữ xây dựng ý tưởng của đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“ ngày thêm một đầy đủ, phong phú, hấp dẫn và ứng dụng mang tình thiết thực hơn. Tôi đầu tiên nghiên cứu tím hiểu tổng quát về ngôn ngữ như Visual C++, thực hiện những chương trính điển hính trên ngôn ngữ lập trính hướng đối tươïng. Và phần tím hiểu chình là phần thực hiện yêu cầu của đề tài, cụ thể là về phương diện tình toán trong những thuật toán và thể hiện trực quan bằng đồ hoạ máy tình trên ngôn ngữ Visual C++. Trong Visual C++ phần đồ hoïa được thể hiện trong lớp CDC (Class Device Context) với nhiều hàm thành viên hỗ trợ cho việc vẽ điểm, đường, đa giác, tô màu…. Đặc biệt hơn trong ngôn ngữ Visual C++ có sự hỗ trợ cho việc vẽ các đối tượng hính học bằng chuột. Nhưng ngôn ngữ chỉ thực hiện được với các đối tượng hính học 2D, đối tượng hính học 3D thí chưa có, cần phải tự thiết kế. Trong quá trính nghiên cứu, tôi nhận thấy trong ngôn ngữ Visual C++ có bộ thư viện OPENGL là một thư viện API hỗ trợ cho việc thực hiện các chương trính đồ họa, trên cả 2D và 3D rất mạnh, chình ví thế ở phần kiểm tra các quan hệ hính học phần 3D tôi thực hiện trên OPENGL. Từ đây tôi chuyển hướng sang nghiên cứu OPENGL để thực hiện cho phần 3D. Để hiểu và thực hiện được trên nó cũng khó khăn không kém như ta bắt đầu nghiên cứu và làm quen với ngôn ngữ mới như Visual C++. Sau khi nghiên cứu và hiểu được những yếâu tố cơ bản của OPENGL tôi có nhận xét rằng OPENGL là một ứng dụng để thực hiện các chương trính đồ họa máy tình hấp dẫn và đẹp mắt. Khi đã cài được thí cách sử dụng có phần dễ dàng hơn, chỉ cần tím hiểu một số các hàm trong thư viện các hàm thành viên của OPENGL là đáp ứng được yêu cầu. Còn mọi việc thực hiện cài đặt theo lý thuyết đồ họa máy tình như các phép biến hính, thiết lập chế độ màn hính, khởi tạo đồ họa, setviewport, tạo các Pallette màu, thiết lập độ sâu hính ảnh, độ phản chiếu hính ảnh, độ tương phản … tất cả do OPENGL hỗ trợ hầu hết. OpenGL được định nghĩa là “giao diện phần mềm cho phần cứng đồ họa ”. Thực chất, OpenGL là một thư viện các hàm đồ họa, được xem là tiêu chuẩn thiết kế công nghiệp cho đồ họa ba chiều. Với giao diện lập trính mạnh mẽ, OpenGL cho phép tạo các ứng dụng 3-D phức tạp với độä tinh vi, chình xác cao, mà người thiết kế không phải đánh vật với các núi công thức toán học và các mã nguồn phức tạp. Và do OpenGL là tiêu chuẩn công nghiệp, các ứng dụng tạo từ nó dùng được trên các phần cứng và hệ điều hành khác nhau. Nhận xét về OPENGL tôi thấy rằng OPENGL là thư viện đồ họa trên WINDOWS bởi ví ta có thể thấy rằng OPENGL không những thực hiện trên ngôn ngữ Visual C++ mà còn có thể cho phép thực hiện trên cả Visual Basis , Borland C++ Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 3 Luaän vaên toát nghieäp II. 2. GIỚI THIỆU CÁC HÀM CỦA NGÔN NGỮ ĐƯỢC SỬ DỤNG a. Các hàm của lớp CDC (Class Device Context) Trong CDC có rất nhiều hàm thành viên phục vụ cho quá trính kết xuất các hính ảnh ra các thiết bị. Trong phần thực hiện đề tài, tôi xin đưa ra các hàm được sử dụng trong đề tài  Vẽ điểm: SetPixel ( int x , int y , int color ); Hàm này thuộc lớp CClientDC trong phần màu sử dụng macro RGB(red,green,blue) Ví du:ï Để vẽ một điểm , ta thực hiện như sau: CClientDC dc( this ); dc.SetPixel (100,100,GRB(0,0,0); Để thể hiện tọa độ một điểm trong hệ trục tọa độ hai chiều, Visual C++ dùng lớp CPoint, đối tượng thuộc lớp này được thể hiện bởi hai thành phần x và y. Vì dụ ta khai báo điểm point như sau: CPoint point point.x=100; point.y=100;  Vẽ đường thẳng: Line (int x1, int y1, int x2, int y2); Hàm này thuộc lớp CClientDC Ví dụ: Để vẽ đường thẳng ta thực hiện các bước sau đây CClientDC dc(this); dc.Line(x1,y1,x2,y2); Ngoaøi ra trong việc vẽ đường thẳng còn có thể sử dụng hai hàm sau: MoveTo(int x, int y); Hàm này dùng để di chuyển con trỏ đến tọa độ x,y trong màn hính. LineTo(int x, int y); Hàm này dùng để vẽ đường thẳng từ điểm hiện hành đến điểm x, y. Cả hai hàm này đều thuộc lớp CClientDC, việc sử dụng như sau: Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 4 Luaän vaên toát nghieäp CClientDC dc(this); dc.MoveTo(x,y); dc.LineTo(newx, newy);  Vẽ hình chữ nhật: Rectangle(int x1,int y1,int x2,int y2); Hàm này thuộc lớp CclientDC. Dùng để vẽ hính chữ nhật có tọa độ trên góc trên trái là (x1,y1) và tọa độ góc dưới phải là (x2,y2). Cú pháp vẽ hính chữ nhật như sau: CClientDC dc(this); dc.Rectangle(x1, y1, x2, y2);  Vẽ hình Ellipse: Ellipse(int x1,int y1,intx2,int y2); Hàm này có các tham tương tự các tham số hính chữ nhật, hàm này cũng thuộc lớp CClientDC. Cú pháp vẽ hính Ellipse như sau: CClientDC dc(this); dc.ellipse(int x1, int y1, intx2, int y2);  Haøm loan vùng kín: FloodFill(int x,int y, int color); Hàm này dùng để tô màu vùng được giới hạn bởi một đường biên khép kìn. Hàm này thuộc lớp CClientDC có tác dụng tô màu với màu color tô hết vùng có tọa độ (x,y) và một vùng kìn bao quanh điểm đó. Cú pháp hàm như sau: CClientDC dc(this); dc.FloodFill(x, y, color);  Tạo các đường vẽ: CreatePen(typeline, width, color); Để tạo đường vẽ trong các ứng dụng vẽ ta xét hàm CreatePen của lớp Cpen, hàm này có dạng như sau: Cpen *pPen=new Cpen; pPen->CreatePen(typeline, width, color); Trong đó :  Tham số typeline là kiểu đường vẽ, nó có giá trị được định nghĩa như sau: PS-SOLID Đường thẳng đồng nhất. Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 5 Luaän vaên toát nghieäp PS-DASH Đường thẳng gồm các gạch ngang đứt nét. PS-DOT Đường thẳng gồm các nét chấm đứt. PS-DASDOT Đường thẳng gồm các gạch ngang chấm đứt. PS-DASHDOTDOT Đường thẳng gồm các gạch ngang chấm đứt. PS-NULL Đường thẳng vô hiệu lực không vẽ ra. PS-INSIDEFRAME Đường thẳng nằm bên trong đường viền.  Tham số width cho độ rộng của nét vẽ tình bằng pixel.  Tham số color cho màu vẽ b. Các hàm trong bộ thư viện OpenGL OpenGL gồm 5 bộ hàm, bộ hạt nhân có 115 hàm cơ bản. Tên các hàm này bắt đầu bằng GL. Windows NT hỗ trợ 4 chủng loại hàm khác, bao gồm thư viện OpenGL utility(tên hàm bắt đầu bằng GLU), thư viện OpenGL auxiliary(tên hàm bắt đầu bằng AUX), bộ hàm”WGL” (tên hàm bắt đầu bằng WGL), và các hàm WIN32 API (tên hàm không có tiền tố đặc biệt). Bộ hàm hạt nhân cho phép thiết kế các hính dạng khác nhau, tạo các hiệu quả chiếu sáng, kết hợp antialiasing và gán cấu trúc, thực hiện biến đổi ma trận… Do các hàm cơ bản được thể hiện ở nhiều dạng khác nhau tùy thuộc vào loại dữ liệu mà chúng tiếp nhận, nên trên thực tế có hơn 300 nguyên mẫu (prototype) các hàm cơ bản.  Thư viện OpenGL utility gồm các hàm cao cấp. Các hàm này đơn giản hoá việc sử dụng hính ảnh cấu trúc, thực hiện việc biến đổi tọa độ mức cao, hỗ trợ tesselation đa giác, và biểu diễn các đối tượng có cơ sở đa giác như hính cầu, hính trụ hính dĩa.  Thư viện OpenGl auxiliary gồm các hàm đặc biệt dùng đơn giản hóa các vì dụ lập trính trong sách chỉ dẫn lập trính OpenGL. Các hàm phụ thuộc platform này thực hiện các nhiệm vụ như quản ký cửa sổ, điều khiển xuất/nhập, vẽ các đối tượng 3D nhất định. Do các hàm này có mực đìch thiết minh nên không được dùng trong các mã sản xuất.  Các hàm “WGL”kết nối OpenGL với WINdows NT, cho phép người lập trính xây dựng và chọn lựa các ngữ cảnh biểu diễn, tạo các bitmap font, các hàm này chỉ dùng trên Windows NT.  Cuối cùng, các hàm Win32 API được dùng giải quyết các định dạng điểm ảnh và tạo bộ đệm đôi. Trong phần này, tôi trính bày một số hàm được sử dụng trong đề tài.  Hàm vẽ điểm, đường, đa giác: Được bắt đầu bởi hàm: glBegin (Glenum mode) Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 6 Luaän vaên toát nghieäp Để chỉ sự bắt đầu những đỉnh của một primitive, tham số mode chỉ kiểu các primitive. Tham số mode có các giá trị sau:  GL_POINTS : chỉ đỉnh được sử dụng là điểm.  GL_LINES : chỉ những đỉnh được dùng để tạo đoạn thẳng.  GL_LINE_STRIP : chỉ những đỉnh được sử dụng tạo đoạn thẳng nhẵn.  GL_TRIANGLES : những đỉnh được sử dụng tạo ra những tam giác.  GL_TRIANGLE_STRIP : những đỉnh được sử dụng tạo ra tam giác có cạnh nhẵn.  GL_POLYGON : những đỉnh được sử dụng tạo ra đa giác lồi. glEnd ( ) Hàm trên dùng để chấm dứt danh sách các đỉnh mà nó chỉ rõ primitive được khởi tạo bởi hàm glBegin. Ví du: Vẽ đường thẳng từ 2 điểm glBegin(GL_LINES) glVertex3f(0.0f, 0.0f, 0.0f); glVertex3f(50.0f, 50.0f, 50.0f); glEnd( );  Hàm chỉ ra tọa độ của điểm, đường, đa giác: glVertex2f (Glfloat x,Glfloat y) glVertex3f (Glfloat x,Glfloat y,Glfloat z)  Hàm biến đổi tọa độ:  glLoadIdentity(); thay thế ma trận hiện hành bởi ma trận đơn vị.  glMultMatrix(); nhân ma trận hiện hành với ma trận được chỉ định.  gl PopMatrix(void); lấy ma trận hiện hành từ stack.  glPushMatrix(void); đẩy ma trận hiện hành vào stack.  glTranslatef (Glfloat x, Glfloat y, Glfloat z); nhân ma trận hiện hành bởi ma trận tịnh tiến.  gl Rotatef(Glfloat Angle, Glfloat x, Glfloat y, Glfloat z); nhân ma trận hiện hành bởi ma trận quay.  Các hàm liên quan đến màu:  glColor3f (Glfloat red, Glfloat green, Glfloat blue); đặt màu hiện hành bởi các thành phần red, green, blue với giá trị từ 0,0 đến 1,0.  glClearColor(GLclampf red, GLclamp green, Glclamp blue, Glclamp alpha); đặt màu cho việc xóa buffer màu. Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 7 Luaän vaên toát nghieäp  glClear(GL_COLOR_BUFFER_BIT); xóa hiện hành . xóa buffer màu, xóa cửa sổ bởi màu  Các hàm liên quan đến aùnh sáng:  glLightf(Glenum light, Glenum pname, GLfloat param);  glLighti(Glenum light, Glenum pname, GLint param); Trong đó:  Tham số light chỉ ra nguồn sáng có giá trị từ GL_LIGHT0 đến GL_LIGHT7.  Tham số pname chỉ ra tham số light nào được lập như GL_AMBIENT, GL_DIFFUSE…  Tham số param chỉ có ý nghĩa đối với nguồn sáng điểm. Tham số này có các giá trị như: GL_SPOT_EXPONENT, GL_SPOT_CUTOFF…  Các hàm liên quan đến thuộc tính ánh sáng của vật liệ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 đó:  face: là thuộc tình bề mặt trước ,sau của đa giác.  pname: là thuộc tình của vật liệu: GL_AMBIENT,GL_DIFFUSE,…  param : chỉ định giá trị mà tham số pname được lập.  params: chỉ định dãy số nguyên hay thực chứa các thành phần thuộc tình được lập.  glFrontFace(Glenum mode); xác định bề mặt đa giác là mặt trước hay sau. PHẦN II: NỘI DUNG Trong phần giới thiệu tôi đã trính bày những nội dung sơ lược mang tình tổng quát của đề tài. Phần nội dung tôi trính bày chi tiết hơn theo thứ tự logic các vấn đề từ lý thuyết toán học đến các thuật toán chương trính. Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 8 Luaän vaên toát nghieäp I. LÝ THUYẾT CƠ SỞ TOÁN HỌC Các lý thuyết cơ sở toán học được sử dụng cho các thuật toán trong đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“ bao gồm:  Hính học giải tìch trong mặt phẳng  Hính học giải tìch trong không gian. Phần lý thuyết cơ sở toán học này rất cần thiết cho việc thiết kế chương trính thực hiện việc kiểm tra các quan hệ hính học, không gian vector là cơ sở lý thuyết toán học tất yếu để xây dựng các cấu trúc đồ họa máy tình. I.1. Giới thiệu về vector: Điểm (point): Mô tả các vị trì của đồ hính và có nhiều cách để diễn đạt. Trong hai chiều biểu diễn bằng cách dùng bộ-2 để cho các tọa độ theo hai trục. Hai dạng thường được áp dụng nhiều đó là dạng Cartesian như (x,y) =(3,4) hay dạng tọa độ cực (R, )=(2.4,450). Trong khi chúng được định nghĩa một cách đại số theo các thao tác nhất định trên đó, chúng cũng cho phép một diễn dịch hính học theo các điểm, đường, chiều. Vector: Nhín một cách hính học, vector là một đoạn thẳng mà các đieåm đầu và điểm cuối đã được xác định . Vector là một đối tượng có độ dài và chiều tương ứng với một số thực thể vật lý như lực, khoảng cách, và vận tốc. Vector thường được vẽ như một mũi tên có chiều dài chỉ về một hướng. Khi vector được chọn để chỉ định hệ tọa độ, các vector có một hàm số để đưa ra hai hằng số, ba hằng số,... Ví thế, một trong các thể hiện của một vector hai chiều a là một cặp có thứ tựï a=(a x , a y ). Trong chương trính, vector được biểu diễn bằng kiểu dữ liệu: Typedef struct { dx,dy: float; } vector; struct { dx,dy,dz : float; } vector3D P2 x P4 v v P1 P5 Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 9 P3 y Luaän vaên toát nghieäp Với hai điểm P1(x1,y1) và P2(x2,y2) ta định nghĩa vector v với các thành phần là vector v =(x2-x1, y2-y1). Đôi khi vector này được ghi là P1P2 và gọi là vector từ P1 đến P2. Bản thân vector không bị buộc vào một vị trì, mặc dù để dễ hính dung thường vẽ chúng xuất phát từ một điểm. Với điểm bất kỳ P = (Px, Py) trong một hệ tọa độ, vector đi từ gốc tọa độ với các tọa độ v=(Px, Py) được gọi là vector vị trì cho P. Vector 3D cũng rất quan trọng trong đồ họa. I.2. Các phép tính vector: Một vector n chiều, với n là số nguyên dương bất kỳ: W=(W1,W2,. . .,Wn) với mỗi thành phần Wi là số vô hướng. Các vector 2 chiều và 3 chiều với n=2, n=3 thí thường gặp nhất trong đồ hoạ Chúng ta không thể thấy được các vector lớn hơn 3 nhưng chúng là những thành phần có giá rị rât lớn. Hai phép tình số học cơ bản trên vector là cộng hai vector và định tỷ lệ một vector.  Cộng hai vector Tổng hai vector a,b là vector c được định nghĩa như sau: C = (c 1 , c 2 , …, c n ) = (a 1 + b 1 , a 2 + b 2 , …, a n + bn ) b a+b a+b b a Hình a Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc a Hình b trang 10 Luaän vaên toát nghieäp Hính a: Các thành phần của tổng là tổng các thành phần của các vector tham gia. Hính b: Tổng các vector là đường chéo hính bính hành. Procedure AddVectors( vector a, vector b; vector &c ); { c.dx := a.dx + b.dx; c.dy := a.dy + b.dy; }  Định tỷ lệ một vector Việc định tỷ lệ một vector nhằm thay đổi độ dài của hay đảo chiều của nó. sa = (sa 1 , sa 2 , …, sa n ) Với s là hệ số tỷ lệ và a là vector. Khi s âm, chiều của sa ngược lại với a. Procedure Scalar(real s; vector a; vector &b) { b.d x = s  a.d x ; b.d y = s a.d y y ; }  Phép trừ hai vector: Trên cơ sở cộng và định tỷ lệ, phép trừ dễ dàng định nghĩa: a-c = a +(-c) với thành phần thứ i là ai-ci. a-c a c -c  Trị tuyệt đối (độ dài) của vector Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 11 Luaän vaên toát nghieäp Nếu một vector W được thể hiện trong không gian nhiều chiều (W 2 , W 2 , …, W n ), dựa theo định lý Pithagore ta có công thức sau: W  (W12  W22  ...  Wn2 ) Vector có độ dài bằng zero thường được gọi là vector 0. Chương trính con minh họa như sau: Function Length(vector v): Real;  Chuẩn hóa vector -Vector đơn vị Việc định tỷ lệ một vector để kết qủa có độ dài bằng 1 gọi là chuẩn hoá một vector, và kết qủa gọi là vector đơn vị. Vì dụ dạng chuẩn hoá ua của a như sau: ua = a / | a| và có cùng chiều với a. Biểu thức cho hệ số của vector có thể khai báo trực tiếp như sau: Normalize(vector v, vector &u); Nó có dạng vector đơn vị u do các hệ số mỗi thành phần của v: u.d x := v.d x /Length(v); u.d y := v.d y /Length(v);  Tổ hợp tuyến tính của vector: Để hính thành tổ hợp tuyến tình của hai vector V và W, định tỷ lệ mỗi vector theo các tỷ số a và b rồi cộng kết qủa để thành vector mới av+bw. Tổng quát, tổ hợp tuyến tình của m vector V 1 , V 2 , …, V m như sau: W = a 1 V 1 + a 2 V 2 + …+ a m V m 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; }  Tổ hợp lồi của vector Một lớp đặc biệt của tổ hợp tuyến tình có vị trì quan trọng trong toán học và ứng dụng số học trong đồ họa, đó là:Tổ hợp lồi (convex combination), hay tổ hợp tuyến tình mà caùc hệ số không âm và tổng bằng 1. Vậy tổ hợp tuyến tình: Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 12 Luaän vaên toát nghieäp W = a 1 V 1 + a 2 V 2 + … +a m V m là tổ hợp lồi nếu tổng một tập các vector. a i =1và a i  0, và cung “spline” thực ra là tổ hợp lồi của  Tích vô hướng của hai vector: Tìch vô hướng của hai vector cho ta thông tin đáng giá về một cặp vector như góc giữa chúng (cụ thể là khi nào chúng vuông góc) và chiếu vector lên vector khác. Nó cũng cho ta phương trính của một mặt phẳng mô tả bằng một điểm vaø hai vector. Cho hai vector, vì dụ hai chiều (a1,a2) và (b1,b2). Tìch vô hướng hai vector định nghĩa là: a.b = a1b1+ a2b2 Một cách tổng quát cho vector n chiều như sau: Cho Vector V= (v 1 , v 2 , …, v n ) và W=( w 1 , w 2 , …, w n ), tìch vô hướng củahai vector trên là: V. W = V W i i với i = 1,… ,n Tìch vô hướng của hai vector được thể hiện trong thủ tục sau: Procedure Float Dot (vector a,b) { return Dot = a.d x * b.d x + a.d y * b.d y ; }  Các tính chất của tích vô hướng 1. 2. 3. 4. Đối xứng : a.b = b.a Tuyến tình: (a+c).b = a.b + c.b Đồng nhất : (sa).b = s(a.b) | b2 | = b.b Độ dài của hiệu và tổng hai vector được cho như sau: | a-b|2 = |a|2 - 2ab + |b|2 | a+b|2 = |a|2 + 2ab + |b|2  Các ứng dụng của tích vô hướng: Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 13 Luaän vaên toát nghieäp a. Góc giữa hai vector (hay hai đường) Đây là ứng dụng quan trọng của tìch vô hướng. Hính a dưới cho thấy góc  giữa hai vector a và b. Các vector này có thể có hai, ba, hay nhiều chiều. Chúng tạo thành hai cạnh của tam giác, và cạnh thứ ba là a-b. Theo hệ thức lượng trong tam giác, ta có : | a-b|2 = |a|2 + |b|2 - 2 |a||b|cos() Từ phương trính này và phương trính | a-b|2 = |a|2 - 2ab + |b|2 ta suy ra được: a.b = |a||b| cos() Nghĩa là cos() = ua.ub a b Hình a Vậy cosin của góc giữa hai vector a và b là tìch vô hướng của dạng chuẩn hóa hai vector.  Dấu cuả vector a.b và sự trực giao Ta biết rằng cos(  ) >0 nếu  < 90 0 cos(  ) <0 nếu  > 90 0 cos(  ) =0 nếu  = 0 Do vậy từ phương trính: cos(  ) = u a .u b ta có góc giữa hai vector như sau:  Nhỏ hơn 90o nếu a.b >0  Bằng 900 nếu a.b = 0  Lớn hơn 90o nếu a.b < 0 Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 14 Luaän vaên toát nghieäp a a a b b a.b>0 b a.b<0 a.b=0 b. Chiếu và phân tích vector: Hính trên ta phân tìch a thành c theo chiều vector b và e. Theo cách này vector c gọi là chiếu trực giao của a lên b. Rõ ràng c có cùng chiều với b, ta còn phải tình độ lớn | c|. Theo phương trình a.b = |a||b|cos(  ) và hệ thức lượng tam giác ta có phương trình: |c| = |a| a.b  = a.u (*) b ab Như thế độ dài của c chỉ phụ thuộc vào độ dài của a. Bây giờ ta hính thành vector c, bằng cách thêm chiều của b. c = |c|.ub Sau đó, kết hợp với phương trính (*) trên ta có: c = ( a.ub)ub c = a.b b |b|2 Ví duï: trong hai chiều, chiếu của a = (6,4) lên b = (1,2) như hính dưới y c e b a Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc x trang 15 Luaän vaên toát nghieäp Hính chiếu của c nằm dài hơn b kể từ gốc, từ phương trính trên ta có độ dài của c là (2.8, 5.6), vector e = a-c = (3.2, -1.6 ). c. Dạng điểm chuẩn cho đường và mặt phẳng Dạng điểm chuẩn cho đường và cho mặt phẳng dùng nhiều trong đồ họa như việc cắt loại bỏ đường bị che và tô đa giác. n y L c A n c x Xét đường L đi qua điểm A = (Ax ,Ay) theo chiều vector c = (cx ,cy), ta có vector n vuông góc với vector c nghĩa là c.n = 0, cũng có nghĩa là c x .n x + c y .n y =0, hay: cy / cx = -nx / ny Điều kiện n trực giao với c cho ta suy ra n có thể là bội số bất kỳ của (c x , cy), có hai chiều đối nhau. Để có phương trính cho đường L, xét điểm bất kỳ R = (x,y) trên L. Vector R phải vuông góc với n, nên n.(R-A) = 0. Ta có thể viết lại như sau: nR=nA, nhưng không thể nhân điểm với vector được. Ta thay vector R bằng r đi từ gốc và thay A bằng a. Như vậy, các tình toán đều phụ thuộc vào việc chọn gốc tọa độ, còn phương trính đường thẳng vẫn phụ thuộc vào gốc không có gí thay đổi. Như vậy ta có: n.r = D Với D = n.a = nx Ax + ny Ay Đây là phương trính điểm chuẩn cho đường. Phương trính này có thể viết dạng quen thuộc như sau: nxx + nyy = D  Mở rộng dạng điểm cho mặt phẳng Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 16 Luaän vaên toát nghieäp Các mặt phẳng cũng có thể biểu diễn ở dạng chuẩn điểm. Một mặt phẳng hoàn toàn được xác định với một điểm S = (sx, sy, sz) nằm trong đó và hướng chuẩn của mặt phẳng. Chuẩn cho mặt phẳng được hiểu là vuông góc với mọi đường trong mặt phẳng. Gọi hướng chuẩn là n= (nx, ny, nz). Với điểm R= (x, y, z) bất kỳ trong mặt phẳng, xây dựng vector từ R đến S, vuông góc với n. n.(R-S) = 0 Thay R-S bằng r -s và dùng tình tuyến tình, ta được: n.r = D với D = n.s Đây là phương trính điểm chuẩn của mặt phẳng. Mọi điểm trên mặt phẳng có cùng tìch vô hướng với chuẩn. Nghĩa là mọi điểm có cùng hính chiếu lên n. Phương trính maët phẳng P thường viết là: Ax + By + Cz = D Tư ø tìch vô hướng của phương trính ta thấy rằng dạng điểm chuẩn thực ra là: nxX + nyY + nz Z = D Với A = nx, B = ny , và C = nz. Điều này cho thấy (A, B, C) là chiều chuẩn của mặt phẳng. Điểm trên mặt gần gốc nhất là điểm chiếu vuông góc của gốc lên mặt. Như vậy nó tỉ lệ với n, gọi là Kn, nên khoảng cách là| Kn |. Ví Kn nằm trên mặt nên n. (Kn)=D. n S d. Kiểm tra nửa không gian trong và ngoài của một điểm Xét điểm Q, giả sử đường E đi qua điểm A và có chuẩn hướng ra n như hính vẽ: E E n  A inside Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 17 Luaän vaên toát nghieäp Góc  giữa n và Q -A < 90 0 , nếu Q nằm phìa ngoài, ví vậy tìch n.(Q - A) > 0. Tương tự, góc  sẽ lớn hơn 90 0 nếu Q nằm phìa trong, ví vậy n.(Q -A) < 0. Cuối cùng,  = 90 0 nếu Q nằm trên E, và n .(Q - A) = 0. Nếu thay Q -A bằng vector q - a và gọi đặt a.n = D, thí đường E được cho bởi phương trính n.p = D, và ta viết lại thủ tục kiểm tra điểm Q với vector biểu diễn q sẽ nằm: 1. Ở nửa không gian phìa ngoài của E nếu q.n > D. 2. Trên E nếu p.n = D. 3. Ở nửa không gian phìa trong của E nếu q.n < D.  Mở rộng cho mặt phẳng Giả sử mặt P qua điểm A và có vector chuẩn hướng ra n thí điểm Q sẽ: 1. Ở nửa không gian phìa ngoài của P nếu T=(q-a).n > 0 2. Trên P nếu (q-a).n=0 3. Ở nửa không gian phìa trong của P nếu (q-a).n<0. e. Cắt đường thẳng với cửa sổ lồi Ta dùng kiểm tra trong-ngoài để xây dựng công cụ cắt hữu hiệu với cửa sổ là đa giác lồi bất kỳ. Cửa sổ W chứa một đa giác lồi cùng với đường thẳng L từ P 1 tới P2. Ta muốn xác định phần thấy của L nằm trong W. Đa giác lồi nên phần trong cửa sổ được định nghĩa là vùng nằm ở nửa không gian phìa trong của mỗi cạnh của W. Đoạn L được kiểm tra đối với mỗi cạnh của W, và phần nằm ở nửa không gian phìa ngoài được loại ra. Sau khi mọi cạnh đã được kiểm tra, phần còn lại của L sẽ nằm trong W.Ta biểu diễn L ở dạng tham số: P(t) = P1 + ct với c = P2 - P1. w P1 L P2 Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 18 Luaän vaên toát nghieäp Với mỗi cạnh cửa sổ, dùng hai giá trị t in và t out để giữ lại vùng của t mà đoạn có thể nằm trong cửa sổ. Nghĩa là không thể thấy đoạn ở ngoài khoảng (t in , t out ). Giá trị bắt đầu cho t in và t out là 0 và 1. Khoảng này liên tục được cắt xén khi xử lý xong mỗi cạnh. Nếu lúc nào khoảng này thành rỗng, thoát ra khỏi thuật giải cắt, và đoạn L hoàn toàn bị cắt. Còn không thí khoảng (t in , t o u t ) xác định phần của L nằm trong cửa sổ. Ví W lồi, mỗi cạnh E của nó có thể cho là đường cho ở dạng điểm chuẩn: n.p = D Với n là chuẩn hướng ra của cạnh. Bây giờ E có thể có một số tính huống so với đường L. P1 n E P1 n c P2 E c P2  E song song L: nếu n trực giao với c (nghĩa là: n .c= 0). Như vậy L sẽ nằm hoàn toàn ở trong hoặc ở ngoài cửa sổ. Để xét tiếp, chọn điểm bất kỳ trên L, là P 1 và kiểm tra trong-ngoài. Đặt p 1 = P 1 - 0 là vector từ gốc tọa độ đến P 1 . L sẽ hoàn toàn nằm trong nếu: p 1 .n < D Ngược lại L hoàn toàn nằm ngoài.  E không song song với L: L phải cắt cạnh E tại ti, để tình ti dùng phương trính: ti=( D - n.p1 ) /n.c Nếu chiều c của nó nhỏ hơn 900 kể từ n ( n.c > 0) thí đường sẽ đi ra. Ngược lại sẽ đi vào. Nếu đi vào, thí phần với t < ti sẽ không thấy được, và t in được gán là ti(nếu Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 19 Luaän vaên toát nghieäp t in < ti). Ngược lại, thí phần với t > ti sẽ không thấy được, và t out được giảm về ti(nếu ti < t out ). Khi kết thúc, giá trị của t in và t out sẽ được thay vào P1+ ct, để có được các điểm đầu của đường bị cắt.  Tích hai vector Tìch vector của hai vector là một vector. Một trong nhiều tình chất hữu dụng của nó là nó trực giao với hai vector ban đầu. Tìch vector chỉ được định nghĩa cho vector ba chiều, nhưng nó cũng áp dụng trong một số vấn đề trong đồ họa liên quan đến đa giác hai chiều. Cho vector a=(ax, ay, az) và b=(bx, by, bz) tìch vector của chúng viết là a x b. Nó được định nghĩa theo các vector đơn vị chuẩ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 các tính chất đại số sau: 1. i x j = k jxk=i ixk=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)  Ý nghĩa hình học của tích vector: 1. ax b trực giao với cả a và b. 2. Độ dài a x b bằng diện tìch hính bính hành xác định bởi a và b. Diện tích này là: |a x b| = |a||b|sin(  ) với  là góc giữa a và b, đo từ a đến b hay ngược lại miễn sao góc nhỏ hơn 180 0 . 3. Chiều của a x b xác định từ quy tắc bàn tay phải khi làm việc trong hệ tay phải.  Tích bộ ba vô hướng Cho ba vector a, b, c kết hợp chúng cho ra số vô 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) Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trang 20