Đề tài Nghiên cứu các kỹ thuật hiển thị mô hình địa hình ba chiều

KH OA C NT T – Đ H KH TN TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC DIỆP CHÍ CƯỜNG – 0012523 NGHIÊN CỨU CÁC KỸ THUẬT HIỂN THỊ MÔ HÌNH ĐỊA HÌNH BA CHIỀU LUẬN VĂN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN Th.s. ĐINH NGUYỄN ANH DŨNG NIÊN KHÓA 2000 – 2004 KH OA C NT T – Đ H KH TN - 1 - Lời cảm ơn Lời  cảm  ơn  đầu  tiên  em  xin  được  gởi  đến  giáo  viên  hướng  dẫn  thầy  Đinh  Nguyễn Anh Dũng,  là người  đã  tận  tình hướng dẫn và chỉ bảo  em  trong  suốt  thời  gian thực hiện đề tài tốt nghiệp này.  Kế đến em xin chân  thành cảm ơn các  thầy cô  trong Khoa Công Nghệ Thông  Tin, trường Đại học Khoa học Tự nhiên đã tạo điều kiện thuận lợi cho chúng em trong  suốt bốn năm học Đại học, tạo cho chúng em có nền tảng kiến thức vững chắc.  Và cũng không quên gởi lời cảm ơn sâu sắc đến gia đình, các anh chị và bạn bè  đã ủng hộ, giúp đỡ và động viên trong những lúc khó khăn trong suốt thời gian học  tập cũng như nghiên cứu.  Mặc dù  đã cố gắng hết hoàn  thành  luận văn  trong phạm vi và khả năng cho  phép, nhưng chắc chắn sẽ không tránh khỏi những thiếu sót, kính mong sự thông cảm  và tận tình chỉ bảo của quý Thầy Cô và các bạn.  Sinh viên thực hiện Diệp Chí Cường KH OA C NT T – Đ H KH TN - 2 - Bố cục Luận văn gồm 6 chương: • Chương 1: Tổng quan là chương mở đầu, giới thiệu về nhu cầu thực tế và lý do thực hiện đề tài. Chương này cũng nêu ra các hướng giải quyết đã được thực hiện. • Chương 2: Các khái niệm nêu lên một số khái niệm cơ bản liên quan đến vấn đề đã nêu. • Chương 3: Thuật toán của Röttger, Chương 4: Thuật toán ROAM và Chương 5: Thuật toán Diamond mô tả chi tiết một vài thuật toán thông dụng hiện nay. Các chương này sẽ trình bày cấu trúc dữ liệu, hoạt động chi tiết của các thuật toán. Cuối cùng sẽ nêu ra những ưu khuyết điểm của các thuật toán. • Chương 6: Tổng kết là chương cuối cùng của đề tài. Chương này nêu ra kết quả đạt được khi thực hiện cài đặt chương trình. KH OA C NT T – Đ H KH TN - 3 - Mục lục Chương 1 Tổng quan ......................................................................................................6 1.1 Giới thiệu vấn đề ...............................................................................................6 1.2 Các hướng giải quyết vấn đề .............................................................................7 Chương 2 Các khái niệm ..............................................................................................10 2.1 Đường ống đồ họa (graphics pipeline)............................................................10 2.2 Cấu trúc biểu diễn đỉnh ...................................................................................11 2.3 Thu nhỏ khung cảnh (scene reduction) ...........................................................11 2.4 Các mô hình hiển thị đồ họa............................................................................12 Chương 3 Thuật toán của Röttger ................................................................................13 3.1 Cấu trúc dữ liệu ...............................................................................................13 3.2 Hiển thị bản đồ địa hình ..................................................................................15 3.3 Phát sinh lưới tam giác ....................................................................................16 3.4 Geomorphing...................................................................................................22 3.5 Clipping ...........................................................................................................23 3.6 Ưu và khuyết điểm ..........................................................................................23 Chương 4 Thuật toán ROAM .......................................................................................25 4.1 Biểu diễn..........................................................................................................25 4.1.1 Cây nhị phân tam giác..............................................................................25 4.1.2 Lưới tam giác động và liên tục ................................................................26 4.2 Tối ưu với hàng đợi kép ..................................................................................29 4.2.1 Hàng đợi phân chia (split queue) .............................................................29 4.2.2 Hàng đợi kết hợp (merge queue) .............................................................30 4.3 Các khái niệm lỗi (error metrics) ....................................................................32 4.3.1 Các biên xếp chồng trong không gian thế giới ........................................33 4.3.2 Sự méo mó hình học ................................................................................33 4.3.3 Hiệu chỉnh Line-of-site (LOS).................................................................36 4.3.4 Các khái niệm khác..................................................................................36 4.4 Cải tiến quá trình hiển thị ................................................................................37 4.4.1 View-frustum culling ...............................................................................37 4.4.2 T-stripping................................................................................................38 4.4.3 Trì hoãn việc tính toán lại độ ưu tiên.......................................................38 4.4.4 Tối ưu lũy tiến (progressive optimazation)..............................................39 4.5 Ưu điểm và khuyết điểm .................................................................................40 4.5.1 Ưu điểm....................................................................................................40 4.5.2 Khuyết điểm.............................................................................................40 Chương 5 Thuật toán Diamond ....................................................................................42 5.1 Biểu diễn..........................................................................................................42 5.1.1 Cây tứ phân tam giác (triangle quadtree).................................................42 KH OA C NT T – Đ H KH TN - 4 - 5.1.2 Các đặc tính..............................................................................................45 5.1.3 Tính liên tục (continuity) của lưới tam giác ............................................45 5.2 Thuật toán Diamond........................................................................................46 5.2.1 Các hàng đợi tam giác..............................................................................47 5.2.2 Thuật toán ................................................................................................48 5.3 Ưu và khuyết điểm ..........................................................................................51 Chương 6 Tổng kết .......................................................................................................52 KH OA C NT T – Đ H KH TN - 5 - Danh sách hình Hình 3-1: Lưới tam giác của bản đồ địa hình 99× . Các mũi tên thể hiện các mối quan hệ cha – con trong cây tứ phân.......................................................................................14 Hình 3-2: Các quạt tam giác được phát sinh đệ qui cho lưới tam giác trong hình 3.1. Dấu gạch chéo chỉ ra các đỉnh được bỏ qua...................................................................16 Hình 3-3: Tiêu chuẩn độ phân giải toàn cục: khoảng cách với kích thước ô trong cây tứ phân. ...............................................................................................................................17 Hình 3-4: Lưới tam giác của một hình phẳng căn cứ vào tiêu chuẩn độ phân giải toàn cục. Các tâm của quạt tam giác có màu trắng và cạnh màu đen....................................17 Hình 3-5: Tính toán độ gồ ghề bề mặt. ..........................................................................19 Hình 3-6: Hạn chế các giá trị d2 của các khối kề nhau nhằm thỏa mãn điều kiện (4). .20 Hình 3-7: Các giá trị d2 được lan truyền từ dưới lên (theo chiều mũi tên). ..................21 Hình 3-8: Lan truyền các giá trị d2 làm cho lưới tam giác tốt hơn gần các cực trị địa phương trong một bề mặt phẳng. ...................................................................................22 Hình 4-1: Mức 0 → 5 của cây nhị phân tam giác. .........................................................26 Hình 4-2: Phép phân chia và kết hợp trên lưới tam giác của cây nhị phân. Quan hệ láng giềng được thể hiện trong tam giác T ở bên trái. ...........................................................28 Hình 4-3: Phép phân chia ép buộc cho tam giác T.........................................................28 Hình 4-4: Các nêm xếp chồng cho miền 1-D phụ thuộc vào v. .....................................33 Hình 4-5: Biên chênh lệch bởi việc chiếu nêm lên màn hình. .......................................35 Hình 4-6: Bên trái là trước khi hiệu chỉnh LOS, bên phải sau khi thực hiện. ...............36 Hình 5-1: Vài mức ban đầu của cây tứ phân tam giác. ..................................................43 Hình 5-2: Định nghĩa tam giác và các mối quan hệ của nó. ..........................................44 Hình 5-3: Phép phân chia và kết hợp. ............................................................................44 Hình 5-4: Tính không liên tục của lưới tam giác. ..........................................................46 Hình 5-5: Hiệu chỉnh lại tính không liên tục cho lưới tam giác. ...................................46 Hình 6-1: Địa hình được hiển thị bằng thuật toán của Röttger......................................52 Hình 6-2 : Địa hình được hiển thị bằng thuật toán ROAM. ..........................................53 Hình 6-3 : Địa hình được hiển thị bằng thuật toán Diamond.........................................54 Hình 6-4 : Địa hình khi được phủ texture. .....................................................................55 KH OA C NT T – Đ H KH TN - 6 - Chương 1 Tổng quan 1.1 Giới thiệu vấn đề Hiện nay, công nghệ thông tin đã xâm nhập vào mọi lĩnh vực của đời sống xã hội. Tin học đã hỗ trợ cho con người rất nhiều. Có thể nói Tin học đã góp phần làm cho cuộc sống ngày càng tươi đẹp và có ý nghĩa hơn. Giờ đây, khi Tin học đã và đang tiến bộ từng ngày làm cho mọi thứ trở nên hiện đại hơn và dễ sử dụng hơn. Cùng với đà phát triển đó, chúng ta cũng phải kể đến sự phát triển của công nghệ ba chiều. Trên thế giới, các hãng sản xuất phần cứng đồ họa hàng loạt tung ra những sản phẩm có tính năng mạnh mẽ và tốc độ xử lý vô cùng nhanh chóng. Bên cạnh đó, công nghệ ba chiều đã ngày càng được ứng dụng rộng rãi từ lĩnh vục thương mại, công nghiệp, giải trí, … đến cả quân sự, không gian, … Do nhu cầu con người ngày càng tăng, việc mô phỏng thế giới thực là điều phải được thực hiện. Từ những ứng dụng thiết kế ba chiều phục vụ cho việc chế tạo máy móc thiết bị, xây dựng nhà ở công trình kiến trúc, đến các ứng dụng mô phỏng thử nghiệm tính năng trong công nghiệp chế tạo xe hơi, máy bay, … Điều này cho thấy công nghệ ba chiều không thể thiếu được đối với cuộc sống. Trong đó chúng ta không thể nào không kể đến việc mô phỏng dữ liệu địa hình trong thế giới thực vào máy tính. Đây là vấn đề được ứng dụng rất rộng rãi chẳng hạn như trong lĩnh vực không gian, máy tính mô phỏng địa hình bề mặt các hành tinh giúp cho công việc nghiên cứu thử nghiệm; trong lĩnh vực giải trí, các trò chơi máy tính cũng đòi hỏi dữ liệu địa hình giúp trò chơi mang tính hiện thực hơn; trong các hệ thống KH OA C NT T – Đ H KH TN - 7 - thông tin địa lý (Geographic Information System – GIS) thì vấn đề này càng không thể thiếu được; … 1.2 Các hướng giải quyết vấn đề Trên thực tế, dữ liệu địa hình vô cùng phức tạp và to lớn, nhưng có nhiều ứng dụng đòi hỏi sự tương tác động thời gian thực từ phía người sử dụng và do đó đòi hỏi phải xử lý nhanh dữ liệu địa hình để thích nghi với dữ liệu đầu vào từ người dùng. Nhiều hệ thống máy tính xử lý đồ họa hiện đại cho phép hiển thị hàng ngàn đa giác được tô bóng hay phủ hình ảnh (texture) ở một tốc độ tương tác. Tuy nhiên, nhiều ứng dụng chứa đựng các mô hình đồ họa với rất phức tạp về mặt hình học vẫn vượt quá khả năng của phần cứng đồ họa. Vấn đề này khá phổ biến trong các ứng dụng xử lý các mô hình bề mặt đa giác rộng lớn, như các chương trình mô phỏng và mô hình hóa địa hình số. Để phục vụ cho các mô hình bề mặt phức tạp mà vẫn quản lý được tốc độ hiển thị thời gian thực, vấn đề này có hai hướng giải quyết, nhưng cả hai đều hướng đến việc xấp xỉ các bề mặt đa giác hay đơn giản hóa dữ liệu ban đầu. Thứ nhất, các phương pháp này sử dụng mô hình với đa độ phân giải. Mô hình phức tạp ban đầu sẽ được tổ chức trong một cấu trúc dữ liệu đơn giản hơn (các mô hình ở nhiều độ phân giải khác nhau), và sau đó, trong quá trình hiển thị, tùy thuộc vào khoảng cách đến điểm nhìn mà quyết định mô hình sẽ được hiển thị ở độ phân giải nào (thường thì khi ở gần điểm nhìn hiển thị chi tiết hơn, khi ở xa điểm nhìn thì hiển thị ít chi tiết hơn). Hướng thứ hai là cũng sử dụng một cấu trúc dữ liệu để đơn giản hóa địa hình ban đầu nhưng thường là cấu trúc dạng cây và điều khác biệt so với hướng trên là cấu trúc này sẽ được xây dựng không phải ở bước tiền xử lý mà ngay trong lúc hiển thị địa hình. Một vài phương pháp xử lý địa hình hiệu quả đã được đưa ra. Cây tứ phân có lẽ là cấu trúc có ưu thế nhất trong các thuật toán địa hình; các phương pháp sử dụng việc thiết lập tính có thể trông thấy (visibility) hay các mức độ chi tiết dựa trên các khối đã KH OA C NT T – Đ H KH TN - 8 - được đưa ra; và các mạng tam giác bất qui tắc (trianglar irregular networks – TINs) là phổ biến trong các thuật toán có mức độ chi tiết liên tục. Các cây tứ phân thích hợp tốt với việc tổ chức cấu trúc dữ liệu theo bản đồ chiều cao hai chiều và do đó nổi bật trong các thuật toán khảm địa hình (terrain tessellation algorithm). Cấu trúc phân cấp của cây tự cung cấp tốt cho view frustum culling và do đó các cây tứ phân thường được sử dụng ở trước các thuật toán địa hình để phục vụ như là một cơ chế lọc (view culling). A. James Stewart đã mô tả một tập hợp tính nhìn thấy phân cấp (hierarchical visibility) cho địa hình, nó được lưu trữ trong một cây tứ phân hoàn chỉnh và có thể được sử dụng để lọc (cull) các vùng rộng lớn một cách hiệu quả. Phương pháp này hoạt động tốt nếu kết hợp với các thuật toán khác có dựa vào việc tính toán LOD. Willem H. de Boer lại mô tả một thuật toán gần gũi hơn với phần cứng mà sử dụng các tập hợp mức độ chi tiết theo khối (block-based level-of-detail) được gọi là GeoMipMaps. Ông ta đã đề nghị một cải tiến cho thuật toán cơ bản để hạn chế hiện tượng vertex poping (các đỉnh xuất hiện đột ngột) có dạng GeoMipMap tam tuyến (trilinear GeoMipMap), xác định LOD khối này với các khối khác; điều này biến đổi dần dần từ thuật toán mức độ ưu tiên theo khối sang thuật toán mức độ ưu tiên liên tục. Một số phương pháp theo hướng cổ điển, như thuật toán Diamond, đều tận dụng các mạng TINs để thực hiện quá trình hiển thị địa hình. TINs là mạng các tam giác trong đó tất cả các tam giác có hình dạng giống nhau nhưng lại thay đổi về kích thước liên quan đến những tam giác khác. Mạng này đã được Lindstrom, Röttger và Duchaineau tận dụng với các dạng khác nhau. Lindstrom đưa ra một thuật toán để có được mức độ chi tiết liên tục trong một lưới chữ nhật sử dụng cây tứ phân thay đổi động và chiến thuật từ dưới lên (bottom-up). Röttger thực hiện ngược lại với Lindstrom, và đưa ra một thuật toán để có được kết quả tương tự bằng cách sử dụng cây tứ phân hoàn chỉnh và được duyệt theo thứ từ từ trên xuống (top-down). KH OA C NT T – Đ H KH TN - 9 - Duchaineau đưa ra thuật toán ROAM nhằm quản lý việc lập lưới tam giác có mức độ chi tiết liên tục bằng cách sử dụng các phép toán phân chia và kết hợp dựa trên đỉnh. Henri Hakl đưa ra thuật toán Diamond tương tự như thuật toán ROAM nhưng có một số cải tiến nhằm tăng tốc độ hiển thị. KH OA C NT T – Đ H KH TN - 10 - Chương 2 Các khái niệm 2.1 Đường ống đồ họa (graphics pipeline) Việc hiển thị đồ họa có liên quan đến việc đơn giản hóa khung cảnh (scene), một tập hợp dữ liệu không gian 3 chiều thành một tập hợp con nhỏ hơn và nhìn thấy được trên màn hình, rồi sau đó là hiển thị tập hợp này. Để hiển thị một khung cảnh chúng ta chú ý rằng một khung cảnh bao gồm nhiều đa giác mà thường là tập hợp các tam giác với các mục đích hiển thị phần cứng. Quá trình hiển thị đi qua đường ống đồ họa thực hiện các phép biến đổi cho các đỉnh của tam giác tùy theo điểm nhìn (point-of-view) hiện tại và sau đó được chiếu từ không gian thế giới sang không gian màn hình tùy theo viewing frustum. Điểm nhìn sẽ quyết định vị trí và hướng từ đó khung cảnh sẽ được hiển thị, trong khi đó viewing frustum lại quyết định phạm vi của vùng nhìn thấy (field-of-view – FOV). Sau khi thực hiện xong phép biến đổi và phép chiếu, tam giác sẽ được chiếu sáng (nghĩa là tính toán độ sáng trên nó) và được cắt xén (clip – nghĩa là chỉ những phần nào nhìn thấy mới được vẽ) và sau đó cuối cùng là vẽ nó lên bộ đệm đồ họa. Một số phương pháp có thể được chấp nhận trong lúc đang vẽ các tam giác như wire-frame, solid, textured và bump-mapped. Wireframe chỉ hiển thị các đường thẳng nối các đỉnh đa giác, solid chỉ hiển thị thông tin màu sắc, texturing sử dụng hình ảnh hay dữ liệu thủ tục được chiếu lên đa giác, bump-mapping phủ hình ảnh lên bề mặt đa giác và sử dụng một số dạng kỹ thuật tô bóng để tạo ra cảm giác độ sâu cho hình ảnh. KH OA C NT T – Đ H KH TN - 11 - 2.2 Cấu trúc biểu diễn đỉnh Các đỉnh của tam giác được sử dụng trong đường ống đồ họa có thể được biểu diễn theo một số cách, đơn giản nhất là danh sách tam giác (triangle-list). Danh sách tam giác chỉ đơn giản là lưu trữ các đỉnh trong một tập hợp bộ ba tương ứng với ba đỉnh của tam giác. Một danh sách tam giác có thể chứa các thông tin thừa, nếu như hầu hết các tam giác đều có các đỉnh chung. Dãy tam giác (triangle-strip) và quạt tam giác (triangle- fan) đều quan tâm đến điều này và đều đưa ra một cấu trúc biểu diễn đỉnh tiết kiệm dung lượng bộ nhớ và thời gian xử lý. Cấu trúc biểu diễn đỉnh theo chỉ mục cung cấp chi phí lưu trữ và hiển thị tốt nhất bằng cách chỉ lưu các đỉnh duy nhất và sử dụng bộ đệm chỉ mục để kết hợp các đỉnh thành tam giác. Bộ đệm chỉ mục tự nó cung cấp một số các biểu diễn tương ứng với danh sách chỉ mục (index-list), dãy chỉ mục (index-strip) và quạt chỉ mục (index- fan). 2.3 Thu nhỏ khung cảnh (scene reduction) Một khung cảnh thường không được hiển thị toàn bộ mà giảm đi thành một tập hợp con. Việc rút gọn này thường được thực hiện bởi culling các tập hợp tam giác. Culling ngụ ý việc loại bỏ khỏi tập con đã hiển thị và quá trình culling có nhiều dạng; ví dụ như khử mặt khuất (backface culling) sẽ loại bỏ đi tất cả các tam giác quay lưng lại với điểm nhìn (nghĩa là pháp tuyến của tam giác không chỉ về phía điểm nhìn. Các dạng khác của culling thường cố gắng loại bỏ đi các tập tam giác, ví dụ như hộp giới hạn (bounding box) bao quanh một tập hợp các tam giác nếu nằm bên ngoài vùng nhìn thầy (field-of-view) thì không có một tam giác nào trong tập hợp đó được hiển thị cả. Một dạng khác của việc rút gọn tam giác được thực hiện trong mức độ chi tiết (level-of-detail – LOD) và sơ đồ LOD liên tục. Những dạng này giảm bớt các tam giác bằng cách tìm một số lượng tam giác ít hơn