Luận văn:Nghiên cứu các kỹ thuật hiển thị mô hình địa hình ba chiều

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

97
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Nghiên cứu các kỹ thuật hiển thị mô hình địa hình ba chiều

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 TN DIỆP CHÍ CƯỜNG – 0012523 H K NGHIÊN CỨU CÁC KỸ THUẬT H HIỂN THỊ MÔ HÌNH ĐỊA HÌNH Đ BA CHIỀU – TT LUẬN VĂN CỬ NHÂN TIN HỌC N C GIÁO VIÊN HƯỚNG DẪN A Th.s. ĐINH NGUYỄN ANH DŨNG O H K NIÊN KHÓA 2000 – 2004
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. TN 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 H 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. K 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è H đã ủ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 TT và tận tình chỉ bảo của quý Thầy Cô và các bạn. N Sinh viên thực hiện Diệp Chí Cường C A O H K -1-
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 TN đã đượ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. H • Chương 3: Thuật toán của Röttger, Chương 4: Thuật toán ROAM và K 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 H 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. TT N C A O H K -2-
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 TN 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 H Chương 3 Thuật toán của Röttger ................................................................................13 3.1 Cấu trúc dữ liệu ...............................................................................................13 K 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 H 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 TT 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 N 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 C 4.3.3 Hiệu chỉnh Line-of-site (LOS).................................................................36 4.3.4 Các khái niệm khác..................................................................................36 A 4.4 Cải tiến quá trình hiển thị ................................................................................37 4.4.1 View-frustum culling ...............................................................................37 O 4.4.2 T-stripping................................................................................................38 4.4.3 Trì hoãn việc tính toán lại độ ưu tiên.......................................................38 H 4.4.4 Tối ưu lũy tiến (progressive optimazation)..............................................39 4.5 Ưu điểm và khuyết điểm .................................................................................40 K 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 -3-
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 TN H K H Đ – TT N C A O H K -4-
Danh sách hình Hình 3-1: Lưới tam giác của bản đồ địa hình 9 × 9 . 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ứ TN 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 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 K 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 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 TT 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 N 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 C 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 A 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 O H K -5-
Chương 1 Tổng quan TN 1.1 Giới thiệu vấn đề H 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ã K 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. H 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 TT 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 N đượ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 C 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 A công nghệ ba chiều không thể thiếu được đối với cuộc sống. O Trong đó chúng ta không thể nào không kể đến việc mô phỏng dữ liệu địa hình H 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 K 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 -6-
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 TN 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 H 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 K ứ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 H 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 TT 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ổ N 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à C 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 A 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 O 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 H không phải ở bước tiền xử lý mà ngay trong lúc hiển thị địa hình. K 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 đã -7-
đượ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 TN đó 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). H 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ể K đượ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 H độ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 TT (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. N 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á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 A liên quan đến những tam giác khác. Mạng này đã được Lindstrom, Röttger và O 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 H 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). K 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). -8-
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ị. TN H K H Đ – TT N C A O H K -9-
Chương 2 Các khái niệm TN 2.1 Đường ống đồ họa (graphics pipeline) H Việc hiển thị đồ họa có liên quan đến việc đơn giản hóa khung cảnh (scene), K 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. H Để 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 TT 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). N Sau khi thực hiện xong phép biến đổi và phép chiếu, tam giác sẽ được chiếu C 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 A 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, O solid, textured và bump-mapped. H 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 K 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. - 10 -
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. TN 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- H 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 K 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 H 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). TT 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 N 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. 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 A 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 O 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 H 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ả. K 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 mà xấp xỉ được một mô hình đã cho. Một - 11 -
LOD đơn giản có thể lưu trữ các đối tượng nhiều hay ít chi tiết của cùng một đối tượng và sử dụng chúng cho phù hợp, trong khi các sơ đồ phức tạp hơn có thể tính toán LOD trong lúc đang thực hiện. Một thuật toán LOD liên tục có thể tạo ra một tập hợp rất lớn các xấp xỉ mà có thể thay đổi chỉ một tam giác. TN 2.4 Các mô hình hiển thị đồ họa Hiển thị đồ họa cố gắng tạo ra cấu trúc biểu diễn ảo cho dữ liệu mô hình để sử dụng trong quá trình hiển thị. Chúng ta phân loại một mô hình để biểu diễn một đối H tượng, nội thất trong nhà, môi trường ngoài trời hay hỗn hợp. K Một đối tượng có thể là các thực thể - bàn, ghế, con người,… Những đối tượng động tương tác với khung cảnh và sở hữu một trí thông minh nhân tạo đều được gọi là H nhân vật. Dữ liệu thô kết hợp với các đối tượng này thường là một tập hợp các đỉnh. Đ Môi trường trong nhà biểu diễn cho các tòa nhà và kiến trúc, thường được nhìn từ bên trong. Một hệ thống cống rãng và một tòa thánh đường đều là ví dụ của môi – trường trong nhà. Tương tự như đối tượng, dữ liệu thô kết hợp với môi trường trong TT nhà thường là tập hợp các đỉnh. Môi trường ngoài trời bao gồm địa hình, núi, rừng và biển, … Dữ liệu địa hình N thường được lưu trữ dưới dạng bản đồ chiều cao (height field). Bản đồ chiều cao là một hình ảnh 2 chiều trong đó giá trị tại mỗi điểm được diễn giải thành chiều cao tại điểm C đó. Bất kỳ một hình ảnh nào cũng có thể là một bản đồ chiều cao. A Các dạng khác nhau của mô hình sở hữu các tính chất khác nhau, nó sẽ làm cho O một phương pháp cụ thể sẽ có được những thuận lợi cho từng mô hình cụ thể hơn là những mô hình khác. Trong báo cáo này chúng ta chỉ chú trọng vào môi trường ngoài H trời và đặc biệt là mô hình địa hình và sẽ mô tả các phương pháp quản lý và hiển thị K hiệu quả. - 12 -
Chương 3 Thuật toán của Röttger TN Năm 1998, Stefan Röttger đã đưa ra một thuật toán CLOD được xây dựng trên công việc của Peter Lindstrom đã thực hiện trước đó. Giả thuyết cơ bản được H Lindstrom đưa ra là việc sử dụng cây tứ phân để tận dụng được bản đồ chiều cao. Sử K dụng phương pháp từ dưới lên, cây tứ phân này được dùng để phát sinh việc khảm (tesselation) LOD liên tục của dữ liệu địa hình theo thời gian thực. H Röttger đề xuất một cơ chế khác nhằm tận dụng việc làm mịn theo chiến thuật Đ từ trên xuống đối với cây tứ phân phân cấp để tạo một quá trình khảm CLOD thời gian thực cho dữ liệu landscape. – 3.1 Cấu trúc dữ liệu TT Cấu trúc dữ liệu bên dưới của thuật toán là một cây tứ phân. Trong thuật toán này, ta giả sử bản đồ địa hình có kích thước 2 n + 1 × 2 n + 1 . Một lưới được tạo ra bởi N thuật toán như trong hình 3.1. C Cây tứ phân được biểu diễn bởi một ma trận các giá trị nhị phân với mỗi tập hợp các mục (entry) cho trọng tâm của khối (block), nếu một nút tương ứng được làm mịn. A Ma trận cây tứ phân của lưới ví dụ trong hình 3.1 được thể hiện như sau: O H K - 13 -
TN H K H Đ – TT Hình 3-1: Lưới tam giác của bản đồ địa hình 9 × 9 . Các mũi tên thể hiện các mối quan hệ cha – con trong cây tứ phân. N Các mục trong ma trận đánh dấu bằng dấu chấm hỏi không cần được thiết lập C trong quá trình tính toán cho lập lưới tam giác, từ đó thuật toán top-down không truy A cập các giá trị này trong một lưới tam giác đã cho. Bởi vì số lượng các nút được viếng thăm trong mỗi frame chỉ phụ thuộc vào chất lượng hiển thị, nhưng không phụ thuộc O vào kích thước của bản đồ địa hình, yêu cầu băng thông bộ nhớ bị hạn chế bởi chất H lượng hình ảnh mà ta mong muốn. K - 14 -
3.2 Hiển thị bản đồ địa hình Bản đồ địa hình được lập lưới tam giác sẽ được vẽ bằng cách duyệt đệ qui toàn bộ cây tứ phân và các entry trong ma trận tương ứng sẽ được thiết lập. Chỉ khi nào duyệt đến lá của cây tứ phân thì một phần quạt tam giác (fan) hay một quạt tam giác hoàn chỉnh được vẽ lên. Các quạt tam giác (triangle fan) rất thích hợp với việc vẽ lưới TN tam giác ở các độ phân giải (resolution) khác nhau: để tránh các bẫy ở những khối kế cận nhau mà có độ phân giải khác nhau, một lưới tam giác thích hợp được tạo ra một H cách đơn giản bằng cách bỏ qua những trung điểm của các cạnh (xem hình 3.2). K Phương pháp này chỉ thực hiện nếu các mức chi tiết (level) của các nút kề nhau chênh lệch không quá 1 đơn vị. Ở cuối phần kế tiếp, chúng ta sẽ xem yêu cầu này được quản H lý như thế nào trong suốt quá trình hiển thị bằng cách tiền xử lý bản đồ địa hình và lưu trữ thông tin về độ gồ ghề của bề mặt Đ Trong quá trình phát sinh các quạt tam giác, chúng ta cần phải quyết định xem – các nút kề nhau có được chia nhỏ ra để có cùng mức chi tiết hay không. Nếu nút láng giềng không được chia nhỏ để có cùng mức chi tiết thì chúng ta có thể bỏ qua trung TT điểm của cạnh chung. Trường hợp này có thể được phát hiện bằng cách kiểm tra các entry trong ma trận tương ứng với nút láng giềng, sau đó được đặt bằng 0 (chú ý rằng N việc truy cập vào các entry ma trận, không được thiết lập, được loại bỏ đảm bảo độ C chênh lệch mức chi tiết nhỏ hơn hoặc bằng 1). A O H K - 15 -
TN H K 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. H 3.3 Phát sinh lưới tam giác Đ Trước khi một khung cảnh được hiển thị như đã mô tả trong phần trước, lưới – tam giác phải được xây dụng bằng duyệt đệ qui cây tứ phân. Ở mỗi nút con, một tiêu chuẩn chia nhỏ nhị phân được đánh giá và kết quả của nó được lưu trữ trong ma trận TT cây tứ phân. Nếu điều kiện thõa mãn và mức chi tiết (level of detail) tốt nhất vẫn chưa đạt tới, thì chúng ta sẽ duyệt sâu xuống cây tứ phân qua tất cả bốn nút con. N Một số khía cạnh cần được quan tâm đến đối với tiêu chuẩn này: trước hết, độ C phân giải nên giảm khi khoảng cách đến điểm nhìn tăng. Điều kiện này có thể được đảm bảo bằng cách thỏa mãn: A l
TN H K 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ứ H phân. Đ Hằng số C điều khiển độ phân giải toàn cục cực tiểu. Nếu C tăng, số lượng toàn bộ các đỉnh trong mỗi frame cũng sẽ tăng theo bậc 4. Chú ý rằng điều kiện trên chỉ – được đánh giá một lần duy nhất cho một quạt tam giác hoàn chỉnh, bao gồm đến 10 TT đỉnh. Để cho phép việc tính toán hiệu quả, việc đo khoảng cách được thực hiện sử dụng L1 –norm. N C A O H 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 K 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 -
Với tiêu chuẩn thứ hai, chúng ta muốn tăng độ phân giải của các vùng có bề mặt gồ ghề cao. Thực tế, chúng ta muốn cực tiểu hóa lỗi của đỉnh đã được chiếu lên màn hình, đây là một đại lượng tốt cho chất lượng hình ảnh. Khi tăng lên một mức chi tiết thì lỗi mới phát sinh ở 5 điểm: ở tâm của nút trong cây tứ phân và 4 trung điểm của các cạnh. Một chặn trên cho lỗi xấp xỉ trong không gian 3 chiều có thể có được bằng cách TN lấy giá trị lớn nhất trong các giá trị chênh lệch độ cao tuyệt đối dhi (xem hình 3.5). Chênh lệch độ cao được tính dọc theo các cạnh và đường chéo của nút, tổng cộng có 6 H giá trị cho mỗi nút. Lỗi trong không gian 3 chiều được phát sinh khi xuống một mức K trong cây tứ phân bây giờ có thể được tính toán bằng cách tính trước giá trị lớn nhất của các giá trị chênh lệch độ cao tuyệt đối, hay xen kẽ với việc tính các giá trị gồ ghề H bề mặt, mà chúng ta gọi là giá trị d2. 1 Đ d2 = (2) max dhi d i =1..6 Các giá trị d2 của một nút nhân với chiều dài cạnh d của nút tương ứng với lỗi – xấp xỉ trong không gian 3 chiều. Do đó, giá trị d2 nhân với d chính là chặn trên cho lỗi TT phát sinh khi tăng một mức chi tiết. Tiêu chuẩn chia nhỏ trên đã chỉnh sửa bao gồm các giá trị d2 cho việc xử lý độ N gồ ghề bề mặt bây giờ có thể đưa ra với biến quyết định f. C l f= d ⋅ C ⋅ max(c ⋅ d 2,1) (3) subdivide if f < 1 A Giá trị hằng số C một lần nữa quyết định độ phân giải toàn cục cực tiểu, nhưng O ngược lại hằng số mới c lại chỉ ra độ phân giải toàn cục mong muốn. Hằng số sau ảnh H hưởng trực tiếp đến số lượng đa giác được hiển thị trong mỗi frame. Do đó, bằng cách K thay đổi c, chúng ta có thể quản lý để có được tốc độ cố định. - 18 -
TN H K Hình 3-5: Tính toán độ gồ ghề bề mặt. H Vấn đề quan trọng còn lại là làm cách nào để đảm bảo chênh lệch mức chi tiết Đ cho các khối kế cận nhau phải nhỏ hơn hoặc bằng 1. Từ đó độ gồ ghề bề mặt của các khối kề nhau có thể khác nhau đáng kể, điều này cần thiết để xây dựng một lưới tam – giác thích hợp mà không có lỗ thủng nào. Sau đây chúng ta sẽ mô tả làm cách nào để TT có được như vậy. Trước tiên giả sử rằng điều kiện (3) được thỏa mãn cho một khối cho trước (f2 < 1), nên khối này được chia nhỏ. Trong trường hợp này, tất cả các khối kề nhau có chiều N dài cạnh gấp đôi cũng phải được chia nhỏ. Do đó, điều kiện sau nhất định phải thỏa C mãn đối với biến quyết định f1 của một khối kề nhau để giới hạn độ chênh lệch mức chi A tiết. l1 l2 O f1 < f 2 ⇔ < (4) d ⋅ d 21 ⋅ d 22 d 2 H Với điểm nhìn nằm ở trong vùng chữ nhật (hình 3.6) biểu thức (3) luôn được K l1 thỏa mãn, khi luôn nhỏ hơn độ phân giải cực tiểu C. Còn nếu nằm bên ngoài vùng d l1 này, thì giá trị phân số bị giới hạn lại trong khoảng từ (khoảng cách điểm nhìn ở 1 2 l2 2 vô cực) và hằng số K. - 19 -