Tài liệu Nghiên cứu một số kỹ thuật rút gọn bề mặt mô hình 3d

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM MINH KHÔI NGHIÊN CỨU MỘT SỐ KỸ THUẬT RÚT GỌN BỀ MẶT MÔ HÌNH 3D LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM MINH KHÔI NGHIÊN CỨU MỘT SỐ KỸ THUẬT RÚT GỌN BỀ MẶT MÔ HÌNH 3D Chuyên ngành : Khoa học máy tính Mã số : 60480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS. ĐỖ NĂNG TOÀN THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá nhân tôi, kết quả của luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu dƣới sự hƣớng dẫn củ PGS TSĐỗ Năng Toàn. Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu khoa học của luận văn này. Thái Nguyên, tháng 12 năm 2015 Học viên Phạm Minh Khôi Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến PGS. TS.Đỗ Năng Toàn người đã tận tình hướng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trình làm luận văn. Em cũng xin gửi lời cảm ơn đến các thầy cô giáo trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên, các thầy cô Viện Công nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ em trong suốt quá trình học của mình. ửi lời cảm ơn tới Ban giám hiệu trường THPT Nguyễn Đức Cảnh - Hải Phòng đã tạo điều kiện thuận lợ tham gia khóa học và quá trình hoàn thành luận văn. ửi lời cảm ơn tới các đồng nghiệp, gia đình và bạn bè những người đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để viên có được kết quả như ngày hôm nay. Thái Nguyên, tháng 12 năm 2015 Học viên Phạm Minh Khôi Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn MỤC LỤC MỞ ĐẦU........................................................................................................................ 1 CHƢƠNG 1. KHÁI QUÁT VỀ ĐỒ HỌA 3D VÀ BÀI TOÁN RÚT GỌN ............................. 3 1.1. Khái quát về đồ họa 3D .......................................................................................... 3 1.1.1. Đồ họa 3D là gì? .............................................................................................. 3 1.1.2. Các thành phần cơ bản của đồ họa 3D. ............................................................... 4 1.1.3. Card màn hình ................................................................................................. 8 1.1.4. Các ứng dụng cơ bản của đồ họa 3D................................................................... 9 1.2. BÀI TOÁN RÚT GỌN ĐỐI TƢỢNG 3D ............................................................... 10 1.2.1. Khái niệm lƣới (Mesh): .................................................................................. 10 1.2.2. Giới thiệu bài toán rút gọn .............................................................................. 11 1.2.3. Một số cách tiếp cận trong rút gọn lƣới 3D:....................................................... 13 CHƢƠNG 2. MỘT SỐ KỸ THUẬT RÚT GỌN BỀ MẶT MÔ HÌNH 3D ............................ 15 2.1. Rút gọn lƣới bằng kỹ thuật PM (Progressive Meshes) ............................................... 15 2.1.1. Ý tƣởng ........................................................................................................ 15 2.1.2. Thuật toán PM (Progressive Meshes) ............................................................... 17 2.1.3. Diện mạo của lƣới: ......................................................................................... 18 2.1.4. Truyền tải lũy tiến .......................................................................................... 20 2.1.5. Nén lƣới ....................................................................................................... 20 2.1.6. Làm mịn có chọn lọc ...................................................................................... 23 2.1.7. Xây dựng lƣới ............................................................................................... 24 2.1.8. Tóm lƣợc: Tối ƣu hóa lƣới .............................................................................. 25 2.1.9. Tổng quan về các thuật toán đơn giản hóa lƣới .................................................. 27 2.1.10. Bảo quản hình dạng bề mặt Edist Espring .................................................... 29 2.1.11. Bảo tồn các thuộc tính vô hƣớngEscalar(M) ....................................................... 30 2.1.12. Duy trì các đƣờng cong gián đoạn (Edisc) ......................................................... 32 2.1.13. Cho phép thay đổi cấu trúc liên kết của các đƣờng cong gián đoạn ..................... 34 2.2. Đơn giản hóa lƣới bằng kỹ thuật Quadric Error Metrics (QEM) ................................. 34 2.2.1. Các yêu cầu về giữ nguyên hình dạng hình học của vật thể (topology preservation) 35 2.2.2. Phƣơng pháp đánh giá độ xấp xỉ ...................................................................... 36 2.2.3. Ý tƣởng và các bƣớc của thuật toán .................................................................. 40 2.2.3.1. Ý tƣởng .................................................................................................. 40 2.2.3.2. Các bƣớc cơ bản của thuật toán ................................................................. 40 2.2.4. Tập các cặp đỉnh sẽ đƣợc xem xét loại bỏ ............................................................. 42 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2.2.4.1. Tập các cặp đỉnh ...................................................................................... 42 2.2.4.2. Phép loại bỏ cặp đỉnh ............................................................................... 43 2.2.5. Hàm xác định giá .............................................................................................. 43 2.2.5.1. Đại lƣợng sai số bậc hai (QEM)................................................................. 45 2.2.5.2. Xác dịnh trọng số của các mặt ................................................................... 47 2.2.5.3. Xác định vị trí đỉnh mới............................................................................ 49 2.2.6. Kiểm tra tính toàn vẹn .................................................................................... 49 CHƢƠNG 3. CHƢƠNG TRÌNH THỬ NGHIỆM .............................................................. 52 3.1. Yêu cầu bài toán .................................................................................................. 52 3.2. Mô tả dữ liệu thử nghiệm. .................................................................................. 52 3.3. Phân tích thiết kế và chƣơng trình thử nghiệm. ........................................................ 54 3.3.1. Phân tích thiết kế ........................................................................................... 54 3.3.2. Chƣơng trình thử nghiệm ................................................................................ 55 3.3.3. Đánh giá kết quả đạt đƣợc ............................................................................... 58 PHẦN KẾT LUẬN ........................................................................................................ 64 TÀI LIỆU THAM KHẢO............................................................................................... 65 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn DANH MỤC HÌNH Hình 1.1. Đối tƣợng 3D ..................................................................................................................... 4 Hình 1.2. Cấu trúc mô hình 3D ......................................................................................................... 5 Hình 1.3. Các đối tƣợng nguyên thuỷ của đa giác............................................................................. 7 Hình 1.4. Mô hình liên tục................................................................................................................. 7 Hình 1.5. Card đồ họa hỗ trợ 3D ....................................................................................................... 9 Hình 1.6. Mô hình lƣới tam giác ..................................................................................................... 10 Hình 1.7. Minh họa về việc giảm thiểu bề mặt 2D.......................................................................... 12 Hình 1.8. Minh họa về việc giảm thiểu bề mặt 3D theo các mức khác nhau .................................. 12 Hình 2.1. Minh họa việc chuyển bó cạnh (ecol: hợp; vsplit: tách) .................................................. 15 Hình 2.2 (a) Trình tự bó cạnh; (b) Kết quả đỉnh tƣơng ứng. ........................................................... 15 Hình 2.3. Minh hoạ của các đƣờng dẫn đƣợc thực hiện bởi tối ƣu hóa bằng cách sử dụng lƣới ba thiết lập khác nhau của Crep ............................................................................................... 26 Hình 2.4. Minh hoạ PM đƣờng dẫn thực hiện thủ tục đơn giản hóa lƣới trong một đồ thị vẽ chính xác so với kích thƣớc mắt lƣới .............................................................................................. 28 Hình 2.5. Đơn giản hóa không sử dụng Edisc ................................................................................. 34 Hình 2.6. Một vật thể gồm nhiều khối hộp đƣợc giảm thiểu theo 2 cách ....................................... 36 Hình 2.7. Mô phỏng tình huống trong không gian hai chiều........................................................... 45 Hình 2.8. Mặt vuông đƣợc “lát” bằng các hình tam giác khác nhau .............................................. 48 Hình 2.9. Sau khi loại bỏ một cặp thì xuất hiện 1 mặt bị ngƣợc. ................................................... 50 Hình 2.10. Giải pháp của QEM ....................................................................................................... 50 Hình 3.1. Ví dụ về yêu cầu rút gọn mô hình 3D.............................................................................. 52 Hình 3.2. Minh họa cấu trúc tệp OBJ .............................................................................................. 53 Hình 3.3. Thử nghiệm mô hình Bunny............................................................................................ 57 Hình 3.4. Thử nghiệm mô hình Dragon .......................................................................................... 58 Hình 3.5. Thử nghiệm mô hình Horse ............................................................................................. 58 Hình 3.6. Bunny 69665 mặt - 34835 đỉnh ...................................................................................... 59 Hình 3.7. Bunny 500 mặt 252 đỉnh ................................................................................................ 59 Hình 3.8. Bunny 100 mặt 52 đỉnh .................................................................................................. 59 Hình 3.9. Dragon 209227 mặt 104855 đỉnh ................................................................................... 59 Hình 3.10. Dragon 500 mặt 250 đỉnh ............................................................................................. 60 Hình 3.11. Dragon 100 mặt 51 đỉnh ............................................................................................... 60 Hình 3.12. Horse 96966 mặt 48485 đỉnh........................................................................................ 60 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Hình 3.13. Horse 500 mặt 252 đỉnh ............................................................................................... 60 Hình 3.14. Horse 100 mặt 52 đỉnh ................................................................................................. 61 Hình 3.15. Car 8160 mặt - 425931 đỉnh ......................................................................................... 61 Hình 3.16. Car 1686 mặt 425931 đỉnh ............................................................................................ 62 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn DANH MỤC TỪ VIẾT TẮT STT Ký hiệu Tiếng Anh Tiếng Việt 1 2D Two- dimensional Không gian hai chiều 2 3D Three-dimensional Không gian ba chiều 3 CPU Central Processing Unit Bộ xử lí trung tâm 4 GPU Graphic Processing Unit Bộ xử lí đồ họa 5 GIS 6 IEEE 7 NURBS 8 PDE GeographicInformation Hệ thống thông tin địa lí System Institute of Electrical and Electronics Engineers Non-Uniform Rational Chuẩn dấu phẩy động số học B- B-spline hữu tỉ không đồng spline Partial Differential Equation đều Phƣơng trình vi phân từng phần Thuật toánlƣới lũy tiếnđơn 9 PM Progressive Meshes giản lƣới biểu diễn bề mặt đa diện Thuật toán đơn giản lƣới biểu 10 QEM Quadric Error Metrics diễn bề mặt đa diện sử dụng độ đo sai số bậc hai 11 RBF 12 VRML Radial Basic Function Hàm cơ sở bán kính Virtual Reality Modeling Ngôn ngữ mô hình hóa thực Language Số hóa bởi Trung tâm Học liệu – ĐHTN tại ảo http://www.lrc.tnu.edu.vn MỞ ĐẦU Hiện nay, công nghệ thông tin đƣợc xem là một ngành mũi nhọn của mỗi quốc gia, đặc biệt là các quốc gia đang phát triển, công cuộc công nghiệp hóa và hiện đại hoá nhƣ nƣớc ta. Sự bùng nổ thông tin và sự phát triển mạnh mẽ của công nghệ kỹ thuật số, công nghệ thực tại ảo đã mở ra nhiều hƣớng mới cho sự phát triển của phần mềm trong đó có lĩnh vực biểu diễn và hiện thị hình ảnh 3D. Trong lĩnh vực biểu diễn, hiển thị hình ảnh 3D có hai phần chính là tạo mô hình bề mặt (Modeling) và tạo sự chuyển động cho mô hình (Animation). Việc tạo mô hình 3D thƣờng thực hiện thông qua sử dụng máy quét 3D hoặc các phần mềm chuyên dụng phổ biến hiện nay là Maya, 3DS Max…, mỗi phần mềm có ƣu việt riêng của mình, song ở Việt Nam 3DS Max đƣợc biết đến nhiều qua việc ứng dụng trong các lĩnh vực thiết kế, kiến trúc, xây dựng. Nhƣng có một đặc tính chung là các phần mềm chỉ chú trọng việc đƣa ra kết quả dƣới dạng phim, ảnh, còn hình ảnh đƣa ra dƣới dạng Object phục vụ cho các hoạt động điều khiển sau đó trong môi trƣờng đồ họa 3D thƣờng là rất nặng, tốn kém nhiều tài nguyên của máy tính. Hiện nay công nghệ phần cứng phát triển mạnh có hỗ trợ cho việc hiển thị hình ảnh 3D, nhƣng vẫn chƣa đáp ứng đƣợc đầy đủ “không gian” cho việc xử lý hình ảnh, tốc độ cao bộ xử lý tuy nhanh song với một mô hình lớn nó cũng trở lên chậm chạp. Vậy vấn đề đặt ra là việc giám thiểu không gian lƣu trữ của mô hình, có thể tích hợp nhiều mô hình với nhau để tạo ra mô hình lớn mà vẫn đáp ứng đƣợc các yêu cầu điều khiển sau đó [1]. Có nhiều kỹ thuật giảm thiều không gian lƣu trữ bằng cách sử dụng các kỹ thuật nén ảnh, nhƣng các kỹ thuật phổ biến hiện nay ngƣời ta thƣờng dùng để giảm thiểu không gian lƣu trữ là loại bỏ bớt số mặt phẳng đa giác biểu diễn của vật thể ban đầu để thu đƣợc mô hình có ít mặt đa giác hơn mà vẫn đảm -1- bảo về mặt hình dạng của mô hình đó. Hiện nay ở nƣớc ta việc ứng dụng công nghệ cao trong các ngành, các lĩnh vực là rất phổ biến trong đó có lĩnh vực đồ họa 3D, song các nghiên cứu về nó còn chƣa nhiều. Từ những lý do kể trên cùng với gợi ý của thầy hƣớng dẫn học viên đã lựa chọn đề tài “Nghiên cứu một số kỹ thuật rút gọn bề mặt mô hình 3D” Đối tượng và phạm vi nghiên cứu - Đối tƣợng nghiên cứu: Mô hình 3D đối tƣợng - Phạm vinghiên cứu: Đối tƣợng riêng lẻ và đƣợc biểu diễn bởi bề mặt lƣới đa giác, quan tâm đến chất liệu che phủ bề mặt. Phương pháp nghiên cứu - Phƣơng pháp nghiên cứu lý thuyết: Tìm hiểu, tổng hợp tài liệu, phân tích, đánh giá các phƣơng pháp. - Phƣơng pháp trao đổi khoa học, lấy ý kiến chuyên gia. - Phƣơng pháp thực nghiệm: xây dựng chƣơng trình cụ thể để thử nghiệm, phân tích, đánh giá kết quả đạt đƣợc. Luận văn gồm ba phần chính: Chƣơng 1. Khái quát về đồ họa 3D và bài toán rút gọn Chƣơng 2. Một số kỹ thuật rút gọn bề mặt mô hình 3D Chƣơng 3.Chƣơng trình thừ nghiệm. -2- CHƢƠNG 1.KHÁI QUÁT VỀ ĐỒ HỌA 3D VÀ BÀI TOÁN RÚT GỌN Nội dung chính của chương sẽ trình bày những khái niệm cơ bản về đồ họa ba chiều theo định hướng của đề tài và sơ lược bài toán rút gọn bề mặt mô hình 3D. 1.1. Khái quát về đồ họa 3D 1.1.1. Đồ họa 3D là gì? Các lĩnh vực đồ họa máy tính liên quan đến việc tạo ra và hiển thị các đối tƣợng ba chiều trong một không gian hai chiều (ví dụ, màn hình hiển thị) là đồ họa 3D. Trong đó, điểm ảnh trong một hình ảnh 2 chiều có các thuộc tính của vị trí, màu sắc, và độ sáng, một điểm ảnh 3D cho biết thêm một thuộc tính chiều sâu cho biết điểm nằm trên một trục Z tƣởng tƣợng. Khi đƣợc kết hợp nhiều điểm ảnh 3D, với mỗi giá trị chiều sâu riêng của mình, kết quả là ta có một bề mặt ba chiều. Ngoài ra, đồ họa 3D cũng hỗ trợ nhiều đối tƣợng tƣơng tác với nhau. Ví dụ, một vật rắn, một phần có thể ẩn đằng sau nó. Cuối cùng, máy tính xử lý với các kỹ thuật sử dụng trong không gian 3D để hiển thị vật thể thực tế với chiều sâu của nó. Mục đích chính của đồ họa 3D là tạo ra và mô tả các đối tƣợng, các mô hình trong thế giới thật bằng máy tính sao cho càng giống với thật càng tốt. Việc nghiên cứu các phƣơng pháp các kỹ thuật khác nhau của đồ họa 3D cũng chỉ hƣớng đến một mục tiêu duy nhất đó là làm sao cho các nhân vật, các đối tƣợng, các mô hình đƣợc tạo ra trong máy tính giống nhƣ thật, có dung lƣợng lƣu trữ và xỉ lý tối ƣu nhất. Và một trong các phƣơng pháp đó là rút gọn mô hình 3D. Có rất nhiều khái niệm khác nhau về đối tƣợng 3D, song một cách chung nhất chúng ta có thể hiểu nhƣ sau: Một đối tƣợng 3D chính là đại diện trừu tƣợng của một đối tƣợng trong thế giới thực hoặc một đối tƣợng do chúng ta tƣởng tƣợng ra đƣợc xây dựng và biểu diễn trong môi trƣờng máy tính. Trong -3- đó, nó bao gồm hai thành phần chính: thứ nhất là một mô hình 3D biểu diễn hình học và màu sắc của đối tƣợng, thứ hai là các thuộc tính, sự ràng buộc và các mối quan hệ giữa các thành phần của đối tƣợng đó. Chúng ta có thể lấy một ví dụ nhỏ về đối tƣợng 3D là một nhân vật đƣợc mô hình hóa và biểu diễn trên máy tính. Nhân vật 3D này sẽ bao gồm: thứ nhất là một mô hình 3D chính là phần hình học và màu sắc để biểu diễn các đƣờng nét, hình dáng của nhân vật (phần tĩnh), thứ hai là các thuộc tính ràng buộc về các cơ quan, bộ phận của nhân vật (phần động), điều này rất quan trọng khi chúng ta thực hiện các thao tác biến đổi lên mô hình để tạo ra sự di chuyển hay thực hiện các hành động của nhân vật. Chúng ta có thể hình dung cụ thể hơn qua Hình 1.1 Hình 1.1. Đối tượng 3D Mô hình 3D của nhân vật hay phần hình học (đƣờng màu xanh thẫm) tạo nên hình dáng của đối tƣợng, sự ràng buộc về cấu trúc (các khung hình xanh lá cây) và các ràng buộc cử chỉ (màu vàng). Tất cả các yếu tố đó tạo nên đối tƣợng nhân vật hoạt hình 3D. 1.1.2. Các thành phần cơ bản của đồ họa 3D. Sence: Là thành phần chứa tất cả các đối tƣợng của không gian 3D, các đối tƣợng này đƣợc lƣu trữ trong cấu trúc dữ liệu dạng cây. -4- Camera: Xác định điểm nhìn mà chúng ta đang xem Sence, đƣợc dùng để thay đổi góc nhìn, hƣớng nhìn, trọng tâm điểm nhìn. Viewport: Là vùng chứa những đối tƣợng mà Camera có thể nhìn thấy, thể hiện một phần trong Sence 3D. Tùy trong từng viewport đối tƣợng có những biến đổi khác nhau, ví dụ nhƣ khi ta nhìn ngôi nhà ở vị trí gần thì các chi tiết, thuộc tính về ngôi nhà đó càng nhiều; ở một góc nhìn khác rất xa thì ta chỉ còn lại hình thù của căn nhà đó (là khối hình hộp) các thông thuộc tính của nó ít đi, thậm chí ta không còn nhìn thấy các ô cửa của nó… Vậy để mô hình đối tƣợng 3D giống nhƣ thế giới thực ta có rất nhiều kỹ thuật phải nghiên cứu, trong đó có rút gọn bề mặt mô hình 3D. Trong khuôn khổ và phạm vi nghiên cứu của luận văn này, mục này chủ yếu trình bày về phần hình học lƣới bao phủ bề mặt của đối tƣợng hay mô hình 3D của đối tƣợng và cụ thể là lƣới tam giác (Phần 1.2.1). Nhƣ đã đề cập, một mô hình 3D bao gồm hai thành phần chính: thứ nhất là cấu trúc hình học tạo nên hình dáng của đối tƣợng (Geometry), thứ hai là chất liệu tạo nên đối tƣợng (Material). Chúng ta có thể hình dung rõ hơn trong Hình 1.2. Ví dụ về cấu trúc của mô hình 3D: Hình 1.2. Cấu trúc mô hình 3D -5- Vertexts: Tập các tọa độ điểm, nó bao gồm 3 giá trị X,Y,Z mô tả về vị trí trong không gian và nó là thành phần nhỏ nhất của một mô hình 3 chiều. Indexs: Tập này sẽ mô tả việc các điểm sẽ kết nối với nhau nhƣ thế nào để tạo nên các đa giác. Geometrys: Là tập các đa giác (tam giác hay tứ giác) tạo nên bề mặt hình học của đối tƣợng. Tập này đƣợc tạo nên từ hai tập trƣớc đó là vertexts và indexs. Textcoords: Tập này sẽ mô tả việc ánh xạ màu sắc lên bề mặt của đối tƣợng. Texture: Là tập màu sắc dùng để ánh xạ lên bề mặt đối tƣợng 3 chiều. Tập này thƣờng là tập các ảnh 2D. Material: Là tập các thuộc tính mô tả tính chất bề mặt của đối tƣợng, nó bao gồm các thông tin mô tả về tính chất của bề mặt nhƣ: độ nhạy sáng, màu sắc, trong suốt hay không trong suốt … Có thể hiểu đây chính là các thông tin mô tả về chất liệu của đối tƣợng. Mỗi một cấu trúc đồ họa thì các thành phần này lại đƣợc tổ chức sắp xếp và lƣu trữ khác nhau, nhƣ trong VRML thì các thành phần này đƣợc tổ chức theo dạng phân cấp hình cây. Các dạng mô hình 3D: Ở đây luận văn chỉ đề cập đến hai dạng mô hình 3D chính là mô hình đa giác (Polygon) rời rạc và mô hình liên tục. Mô hình đa giác (Polygon) Mô hình đa giác là các dạng mô hình mà ở đó bề mặt của đối tƣợng bao gồm nhiều bề mặt đa giác phẳng, có thể tạo ra đối tƣợng từ một bề mặt đa giác hoặc một mạng các bề mặt đa giác. Ta có thể sử dụng bề mặt đa giác để mô hình bất kỳ hình dáng bề mặt nào và đặc biệt hữu ích đối với những dạng đơn giản, với đối tƣợng thuộc lớp động vật, ngƣời, đối tƣợng đòi hỏi một cái nhìn tổng quan với độ trơn cao. Các đối tƣợng nguyên thuỷ của polygon bao gồm (Hình 1.3): -6- Hình 1.3. Các đối tượng nguyên thuỷ của đa giác Mô hình liên tục là các dạng mô hình mà ở đó đối tƣợng ba chiều đƣợc tạo nên bằng cách áp dụng các phƣơng trình toán học nhƣ: B-Spline, NURBS, RBF, PDE… cho việc mô hình hóa (Hình 1.4 là một ví dụ về sử dụng hàm PDE cho mô hình hóa). Hình 1.4. Mô hình liên tục Mỗi một dạng mô hình 3D lại có ƣu nhƣợc điểm rất khác nhau, và tùy vào ứng dụng mà chúng ta lựa chọn biểu diễn đối tƣợng theo dạng nào. Nếu biểu diễn đối tƣợng bằng cách sử dụng các mô hình đa giác rời rạc thì có ƣu điểm là dễ thiết kế, đơn giản, nhƣng nhƣợc điểm là tính toán chậm, khả năng kết nối giữa các mô hình khác nhau một cách tự động là khó khăn. Mô hình liên tục, vì sử dụng các phƣơng trình toán học để biểu diễn nên nó có tính toàn -7- cục cao, khả năng kết nối tốt, nhƣng nhƣợc điểm là phức tạp. 1.1.3. Card màn hình Ngay từ những ngày đầu tiên của máy vi tính, hầu hết Card màn hình làm nhiệm vụ là bộ chuyển đổi, những hình ảnh đƣợc tạo bởi bộ vi xử lí CPU thực hiện và chuyển đổi thành những tín hiệu điện để hiển thị trên màn hình. Để làm đƣợc việc này hầu hết những hình ảnh đƣợc CPU xử lí cùng với những hiệu ứng âm thanh, tín hiệu đầu vào (đối với Game) và những ngắt hệ thống. Bộ vi xử lí của máy tính phải thực hiện mọi công việc để tạo nên những hình ảnh 3D, âm thanh nổi.... điều này sẽ trở nên quá tải đối với những hệ thống thậm chí có bộ vi xử lí tốc độ nhanh nhất và nó không thể phục vụ những yêu cầu nhƣ vậy trong thời gian thực. Để giải quyết đƣợc điều này bộ vi xử lí đồ hoạ, GPU, sẽ tham gia vào công việc tạo nên những hình ảnh và những hiệu ứng 3D. GPU chia sẻ nhiệm vụ với CPU để tạo ra những hình ảnh động với những tốc độ chấp nhận đƣợc. Nhƣ chúng ta đã xem, bƣớc đầu tiên để tạo hình ảnh số 3D là tạo ra hình ảnh với cấu trúc dây (Wireframe) từ những hình tam giác và đa giác.Với những Wireframe đƣợc chuyển từ những thuật toán 3 chiều thành những mẫu mà hiển thị trên màn hình 2D. Hình ảnh biến đổi đƣợc phủ lên bề mặt hoặc đƣợc diễn tả, ánh sáng từ những nguồn sáng khác nhau và cuối cùng thành những mẫu mà hiển thị trên màn hình. Hiện nay hầu hết các Card màn hình đều dùng GPU và nhiệm vụ của nó là diễn tả hình ảnh từ dạng Wireframe do CPU tạo ra và chuyển chúng thành những hình đa giác kiểu 2D. -8- Hình 1.5. Card đồ họa hỗ trợ 3D 1.1.4. Các ứng dụng cơ bản của đồ họa 3D. Ðồ họa máy tính là một trong những linh vực lý thú nhất và phát triển nhanh nhất của tin học. Ngay từ khi xuất hiện nó đã có sức lôi cuốn mãnh liệt, cuốn hút rất nhiều ngƣời ở nhiều lĩnh vực khác nhau nhƣ khoa học nghệ thuật, kinh doanh, quản lý...Tính hấp dẫn của nó có thể đƣợc minh họa rất trực quan thông qua các ứng dụng của nó. Xây dựng giao diện ngƣời dùng (User Interface): Giao diện đồ hoạ thực sự là cuộc cách mạng mang lại sự thuận tiện và thoải mái cho ngƣời dùng ứng dụng. Tạo các biểu đồ trong thƣơng mại, khoa học, kỹ thuật.Các ứng dụng này thƣờng đƣợc dùng để tóm lƣợc các dữ liệu về tài chính, thống kê, khoa học, toán học… giúp cho nghiên cứu, quản lý… một cách có hiệu quả. Thiết kế với sự trợ giúp của máy tính: Trong các lĩnh vực cơ khí, chế tạo nhƣ: chế tạo ô tô, máy bay... để nhằm giảm thiểu chi phí vẫn có chất lƣợng tốt nhất. Lĩnh vực giải trí, y tế,nghệ thuật: Các game chiến thuật, địa hình, mô phỏng các vụ án, các vụ phóng tên lửa đạn đạo, mô phỏng các bộ phận cơ thể con ngƣời trong y tế… Lĩnh vực bản đồ (Cartography): Các bản đồ về địa hình, du lịch, giao thông ngày nay ứng dụng rất tốt công nghệ 3D nhƣ: Google Map; Google -9- Earth; Chỉ dẫn giao thông Sygic với mức tƣơng tác rất cao, cho phép ngƣời dùng bổ sung các địa điểm trên bản đồ, các trạm xăng trên các chặng đƣờng và tình hình ùn tắc giao thông về hệ thống… Giáo dục và đào tạo: Giáo dục đào tạo đã và đang tăng cƣờng ứng dụng công nghệ thông tin trong quản lý giáo dục và giảng dạy, các thầy cô giáo dần làm quen với giáo án điện tử, E_learning, lớp học ảo…; học sinh đƣợc học bài giảng trực tuyến, đào tạo từ xa…; trong các tiết học thực hành với chi phí về đồ dùng thí nghiệm đắt đỏ thì việc ứng dụng các phần mềm thí nghiệm ảo để mô phỏng các thí nghiệm vật lí, hóa học và các chi tiết máy trong môn Công nghệ là vô cùng hiệu quả, học sinh có thể thay đổi các tham số của chƣơng trình để có các ca thí nghiệm khác nhau. Nhƣ vậy tiết kiệm đƣợc chi phí, vẫn đảm bảo tốt mục tiêu giáo dục. Trong lĩnh vực quốc phòng an ninh: Mô phỏng các vụ nổ, tập lái ô ô, máy bay, mô phỏng chiến trƣờng và các tình huống giả định trong chiến đấu. Và nhiều ứng dụng khác 1.2. BÀI TOÁN RÚT GỌN ĐỐI TƢỢNG 3D 1.2.1. Khái niệm lƣới (Mesh): Định nghĩa 1: Lƣới tam giác (Triangle mesh) là một loại của đa giác lƣới trong đồ họa máy tính. Nó bao gồm một tập hợp các hình tam giác đƣợc kết nối bởi các cạnh hoặc góc chung của nó. Hình 1.6. Mô hình lưới tam giác Định nghĩa 2: Khối đa giác (Polygon mesh) là một tập các đỉnh, cạnh và mặt để xác định hình dạng của mô hình đối tƣợng 3D đồ họa máy - 10 - tính và mô hình vật rắn. Các mặt của khối thƣờng bao gồm các hình tam giác, tứ giác, hoặc đa giác lồi, điều này giúp đơn giản hoáviệc dựng hìnhđối tƣợng (có thể bao gồm các đa giác lõm hoặc đa giác có lỗ). Trong luận văn này tập trung vào giải quyết các mô hình dạng lưới tam giác, lƣới tam giác M (V ,F) là một cặp, trong đó có chứa một danh sách các đỉnh V và một danh sách các mặt hình tam giác F. Cả danh sách đỉnh V (v1, v2 ,..., vm ) và danh sách mặt F ( f1, f 2 ,..., f n ) là một tập hợp có thứ tự các chỉ số của nó. Mỗi chỉ số của danh sách có thể truy cập với một số nguyên duy nhất. Mỗi đỉnh là một vector cột trong không gian Euclide  3 . xi vi yi zi Mỗi mặt tam giác trong mô hình bao gồm ba số nguyên đại diện cho ba chỉ số các góc (v j , vk , vl ) của mặt fi fi ( j1, k , l ) Để mô tả một lƣới tam giác, hai loại thông tin cần có: - Thông tin hình học: Thông tin không gian của tất cả các tọa độ đỉnh - Thông tin liên kết: Kết nối các đỉnh để tạo thành các cạnh và mặt 1.2.2. Giới thiệu bài toán rút gọn Khái niệm rút gọn lưới:Rút gọn mô hình 3D là[3] nghiên cứu một lớp các thuật toán nhằm giảm thiểu số mặt của một lƣới bề mặt sao cho vẫn giữ lại đƣợc một cách tƣơng đối hình dạng ban đầu của vật thể đó (Hình 1.8). Cụ thể là: Thu đƣợc lƣới mới có ít mặt, cạnh, và đỉnh nhƣng vẫn giữ đƣợc hình dạng của lƣới ban đầu càng nhiều càng tốt; làm giảm sự phức tạp của một lƣới đã cho. Để giảm thiểu không gian bộ nhớ của mô hình, một trong những cách tiếp cận là giảm thiểu số bề mặt biểu diễn mô hình.Các thuật toán "giảm thiểu - 11 -