Nghiên cứu 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 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

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

- 1 -

Diệp Chí Cường

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

- 2 -

kết quả đạt được khi thực hiện cài đặt chương trình.

Mục lục

4.1.1 4.1.2 4.2

4.2.1 4.2.2

4.3.1 4.3.2 4.3.3 4.3.4

4.4.1 4.4.2 4.4.3 4.4.4

- 3 -

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 Cây nhị phân tam giác..............................................................................25 Lưới tam giác động và liên tục ................................................................26 Tối ưu với hàng đợi kép ..................................................................................29 Hàng đợi phân chia (split queue) .............................................................29 Hàng đợi kết hợp (merge queue) .............................................................30 4.3 Các khái niệm lỗi (error metrics) ....................................................................32 Các biên xếp chồng trong không gian thế giới ........................................33 Sự méo mó hình học ................................................................................33 Hiệu chỉnh Line-of-site (LOS).................................................................36 Các khái niệm khác..................................................................................36 4.4 Cải tiến quá trình hiển thị ................................................................................37 View-frustum culling ...............................................................................37 T-stripping................................................................................................38 Trì hoãn việc tính toán lại độ ưu tiên.......................................................38 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 Khuyết điểm.............................................................................................40 4.5.2 Chương 5 Thuật toán Diamond ....................................................................................42 5.1 Biểu diễn..........................................................................................................42 Cây tứ phân tam giác (triangle quadtree).................................................42 5.1.1

5.1.2 5.1.3 5.2

5.2.1 5.2.2

- 4 -

Các đặc tính..............................................................................................45 Tính liên tục (continuity) của lưới tam giác ............................................45 Thuật toán Diamond........................................................................................46 Các hàng đợi tam giác..............................................................................47 Thuật toán ................................................................................................48 5.3 Ưu và khuyết điểm ..........................................................................................51 Chương 6 Tổng kết .......................................................................................................52

Danh sách hình

99 × . Các mũi tên thể hiện các mối quan

- 5 -

Hình 3-1: Lưới tam giác của bản đồ địa hình 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

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

- 6 -

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

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

- 7 -

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 đã

đượ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ừ

- 8 -

từ trên xuống (top-down).

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

- 9 -

có một số cải tiến nhằm tăng tốc độ hiển thị.

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

- 10 -

tô bóng để tạo ra cảm giác độ sâu cho hình ảnh.

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

- 11 -

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

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.

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

tượng, nội thất trong nhà, môi trường ngoài trời hay hỗn hợp.

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à

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

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

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

đó. Bất kỳ một hình ảnh nào cũng có thể là một bản đồ chiều cao.

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

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

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ị

- 12 -

hiệu quả.

Chương 3

Thuật toán của Röttger

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

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ử

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.

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

×+

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

. Một lưới được tạo ra bởi

này, ta giả sử bản đồ địa hình có kích thước thuật toán như trong hình 3.1.

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.

- 13 -

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:

99 × . Các mũi tên thể hiện các mối quan

Hình 3-1: Lưới tam giác của bản đồ địa hình

hệ cha – con trong cây tứ phâ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

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

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

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

- 14 -

lượng hình ảnh mà ta mong muốn.

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

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

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

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

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

đ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

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 độ

- 15 -

chênh lệch mức chi tiết nhỏ hơn hoặc bằng 1).

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.

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

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.

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, độ

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:

l d

(1)

với một số hằng số C, trong đó l là khoảng cách từ điểm nhìn, và d là chiều dài cạnh

- 16 -

của khối (xem hình 3.3 và 3.4). C là một tham số chất lượng có thể cấu hình lại được.

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.

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

1L –norm.

đỉ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

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

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

idh (xem hình 3.5).

lấy giá trị lớn nhất trong các giá trị chênh lệch độ cao tuyệt đối

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

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

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ề

bề mặt, mà chúng ta gọi là giá trị d2.

dh i

max 6..1 i =

1 d

(2)

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

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ý độ

)1,2

gồ ghề bề mặt bây giờ có thể đưa ra với biến quyết định f.

l max( Cd dc ⋅ ⋅ ⋅ subdivide 1 if f <

(3)

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

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ưở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

- 18 -

thay đổi c, chúng ta có thể quản lý để có được tốc độ cố định.

Hình 3-5: Tính toán độ gồ ghề bề mặt.

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 để

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

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

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

tiết.

f ⇔< 2

l 2 d

l 1 dd ⋅

d ⋅ 2

(4)

l1 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

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

1 (khoảng cách điểm nhìn ở

thỏa mãn, khi d

l 1 2l

này, thì giá trị phân số bị giới hạn lại trong khoảng từ 2

- 19 -

vô cực) và hằng số K.

1 2

l 1 2 l

2 L 1 2 L

C C −

(5)

thỏa mãn

d d

1 1 2

l 1 2l

lớn hơn K, sau đó điều kiện (4) thỏa mãn, khi Mặt khác, nếu

điều kiện (5). Tuy nhiên, khi giá trị d2 tương ứng với độ gồ ghề bề mặt, có thể tăng lên

2 d ≤ 1 2 d

, sau đó chúng ta một cách tùy ý, điều kiện (4) không tự thỏa mãn. Do đó, nếu

phải thay đổi các giá trị d2 như sau: Bắt đầu với khối tồn tại nhỏ nhất, chúng ta tính các

giá trị d2 cục bộ của tất cả các khối và lan truyền chúng trong cây. Giá trị d2 của mỗi

khối là giá trị cực đại của giá trị cục bộ và K nhân với các giá trị đã tính từ trước đó của

các khối kề nhau ở mức chi tiết thấp hơn kế tiếp. Trong ví dụ này, các giá trị d2 được

lan truyền từ lá lên gốc của cây tứ phân thể hiện trong hình 3.7.

- 20 -

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

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

Đến đây, chúng ta chỉ xem xét trường hợp 2 chiều, nhưng với một vài chú ý

chúng ta có thể chấp nhận nó trong 3 chiều. Trong trường hợp này, độ cao của điểm

nhìn cần phải được quan tâm liên quan đến tâm của các ô trong cây tứ phân. Tuy nhiên,

khi bản đồ chiều cao thường có chiều cao nhỏ hơn so với kích thước của chúng,

khoảng cách này có thể được xấp xỉ bằng độ chênh lệch giữa điểm nhìn và độ cao

trung bình của các nút trong cây tứ phân.

Ví dụ về ảnh hường của sự lan truyền các giá trị d2 khắp bản đồ chiều cao, và

ảnh hưởng của nó lên lưới tam giác đã cho trong hình 3.8. Có một số cực trị nằm trên

- 21 -

bề mặt phẳng.

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.

3.4 Geomorphing

Đến đây, chúng ta chỉ ra làm thế nào để lập lưới tam giác và hiển thị một bản đồ

địa hình, nhưng hiện tượng popping khi điểm nhìn di chuyển vẫn xảy ra. Nhớ rằng biến

quyết định f từ biểu thức (3): Kiểm tra thấy rằng nếu f nằm trong khoảng , thì cây

[ 1,2 )

1 chỉ ra rằng nút đó có ít nhất một nút con, trong khi các giá trị lớn

tứ phân không được làm mịn hơn nữa, và một quạt tam giác được tạo ra cho nút này.

Các giá trị nhỏ hơn 2

hơn 1 thì nút đó không có nút con nào cả.

1(2

)

−

Nếu morphing chỉ xảy ra ở các nút lá của lưới tam giác hiện tại, chúng ta có thể

sử dụng được giới hạn trong đoạn [0, 1] như là một hệ số blend cho những

chỗ ranh giới giữa hai mức chi tiết (xem hình 3.5). Phụ thuộc vào các nút kề nhau trong

cây tứ phân được chia nhỏ sâu đến bao nhiêu, có đến 5 đỉnh mà phải thực hiện

morphing cho mỗi nút trên cây (xem hình 3.2 và 3.6). Độ cao ở những điểm này được

nội suy tuyến tính với hệ số b giữa độ cao của mức chi tiết thấp nhất (là trung bình của

hai điểm góc tương ứng) và độ cao của mức chi tiết cao nhất có thể lấy trực tiếp từ dữ

liệu bản đồ chiều cao.

Cần phải cẩn thận để tránh các hiện tượng xuất hiện các vết nứt (cracks) và tạo

- 22 -

ra một lưới cho phù hợp. Các hệ số blending của các khối kế cận hơi khác nhau căn cứ

vào việc thay đổi khoảng cách đến điểm nhìn. Do đó, độ cao nội suy ở trung điểm của

cạnh chung là khác nhau đối với các khối kề nhau, nên làm cho các vết nứt xuất hiện.

Để tránh hiện tượng này, chúng ta lưu các hệ số blending trong ma trận nhị phân.

Giá trị blending cho cạnh chung có được bằng cách lấy cực tiểu các giá trị blending của

hai khối. Giá trị bằng 0 chỉ ra rằng không chia nhỏ nữa, trong khi các giá trị biểu diễn

cho các hệ số blending. Chúng ta tránh lưu trữ các giá trị số thực bằng cách sử dụng

một byte cho mỗi entry. Kết quả chúng ta có 255 bước morphing, đủ chính xác trong

thực tế.

3.5 Clipping

Một cải tiến phổ biến để giảm số lượng đa giác hiển thị đó là clipping với

viewing – frustum. Khi chúng ta sử dụng cây tứ phân, chúng ta cũng có thể sử dụng nó

cho việc clipping. Như đã cung cấp, mức chi tiết không quá cao, hộp giới hạn

(bounding box) được tính toán cho mỗi nút, để có thể sử dụng cho clipping với

viewing-frustum. Theo cách này, hầu hết các đỉnh không nhìn thấy có thể được loại bỏ

ở giai đoạn sớm của thuật toán một cách ít tốn kém. Clipping có thể được áp dụng cho

cả hai quá trình phát sinh lưới tam giác và quá trình hiển thị. Đối với quá trình phát

sinh lưới tam giác chúng ta xem như hộp giới hạn lớn gấp 3 lần, bởi vì các hệ số

blending của một số khối có thể góp phần vào quá trình phát sinh lưới tam giác mà các

khối đó không được nhìn thấy.

3.6 Ưu và khuyết điểm

Ưu điểm chính của thuật toán này là nhu cầu dụng lượng bộ nhớ cho cấu trúc

biểu diễn là ít hơn so với các thuật toán khác. Một lần thiết lập, thuật toán yêu cầu chỉ

một byte phụ cho mỗi phần tử dữ liệu địa hình. Byte này lưu giá trị variance và làm

- 23 -

mịn nút của toàn bộ cây. Không có không gian bộ nhớ cố định phụ nào yêu cầu thêm.

Khuyết điểm chính của thuật toán này là thiếu sơ đồ hiển thị cố kết frame (frame

corehency). Tính cố kết frame tận dụng dữ liệu khảm của frame trước đó để tạo ra lưới

kết quả của frame hiện tại. Cơ chế này thực hiện công việc có độ phức tạp O(số lượng

tam giác thay đổi), thường khoảng nhỏ hơn 5% mỗi frame. Thuật toán của Röttger có

nn × điểm dữ liệu.

- 24 -

độ phức tạp O(log n), với bản đồ chiều cao có

Chương 4

Thuật toán ROAM

Thuật toán ROAM (Real-time Optimally Adapting Meshes) được Mark

Duchaineau đưa ra năm 1997. Thuật toán này tận dụng quá trình phân chia và kết hợp

để tạo ra lưới tam giác một cách hiệu quả. Ý tưởng tận dụng các thủ tục phân chia và

kết hợp để tạo ra lưới tam giác gắn kết frame (frame coherency – nghĩa là lưới tam giác

của frame này sẽ được xây dựng từ lưới tam giác của frame trước đó thông qua phép

phân chia và kết hợp) đã được xúc tiến bởi Lindstrom trước đó – nhưng Duchaineau đã

quan sát những hàm ý bên trong những khái niệm về cây nhị phân tam giác và sau đó

phát biểu có hệ thống lại thành thuật toán ROAM rất thành công. Thuật toán này ngày

nay được sử dụng rộng rãi trong rất nhiều ứng dụng liên quan đến địa hình. Và hiện

nay người ta còn áp dụng thuật toán này vào việc hiển thị một đối tượng tổng quát.

4.1 Biểu diễn

4.1.1 Cây nhị phân tam giác

Nếu cây tứ phân theo dạng hình vuông có bản sau là cây tứ phân tam giác, thì

cây nhị phân theo dạng hình chữ nhật quen thuộc lại có bản sau là cây nhị phân tam

giác ít được biết đến. Hình dưới đây thể hiện vài mức đầu của cây nhị phân tam giác.

Tam giác gốc T = (va, v0, v1) được định nghĩa là một tam giác vuông cân ở mức (level)

thô nhất, l = 0. Ở mức kế tiếp tốt hơn, l = 1, các con của tam giác gốc được định nghĩa

bằng cách phân chia tam giác gốc theo đoạn thẳng nối từ đỉnh của tam giác va tới trung

- 25 -

điểm vc của cạnh huyền (v0, v1). Tam giác con trái của T là T0 = (vc, va, v0), trong khi đó

tam giác con phải của T là T1 = (vc, v1, va). Phần còn lại của cây nhị phân tam giác

được định nghĩa bằng cách đệ qui lặp đi lặp lại tiến trình phân cách này.

Hình 4-1: Mức 0 → 5 của cây nhị phân tam giác.

4.1.2 Lưới tam giác động và liên tục

Các lưới điểm trong không gian thế giới được hình thành bằng việc gán các vị

trí trong không gian thế giới w(v) cho các đỉnh của cây nhị phân. Một tập hợp các tam

giác của cây nhị phân tạo thành một lưới điểm liên tục khi không có bất kì hai tam giác

nào chồng lên nhau ở bất kì đâu ngoại trừ chúng có chung đỉnh và chung cạnh. Chúng

ta chỉ quan tâm đến những lưới liên tục như lưới tam giác cho cây nhị phân hay đơn

giản là lưới tam giác (triangulation). Hình 4.2 mô tả một láng giềng điển hình của tam

giác T trong lưới tam giác. Chúng ta định nghĩa TB là láng giềng đáy (base neighbor)

chia sẻ cạnh huyền (v0, v1), TL là láng giềng trái (left neighbor) chia sẻ cạnh trái (va, v0),

và TR là láng giềng phải (right neighbor) chia sẻ cạnh phải (v1, va) của tam giác.

Một điểm then chốt về lưới tam giác cho cây nhị phân là các láng giềng đó đều

- 26 -

có cùng mức (level) l với T, hay có mức tốt hơn liên tiếp l + 1 đối với các láng giềng

trái và phải, hay có mức thô hơn liên tiếp l – 1 đối với các láng giềng đáy. Tất cả các

quan hệ này được mô tả thông qua các tam giác trong Hình 4.3.

Khi T và TB đều có cùng mức l, chúng ta xem cặp (T, TB) như là một hình thoi

(diamond). Phép phân chia và phép kết hợp (phép đảo của phép phân chia) cũng được

mô tả trong Hình 4.3 cho lưới tam giác có chứa hình thoi. Phép phân chia sẽ thay thế

tam giác T bằng các tam giác con (T0, T1), và tam giác TB bằng hai tam giác con (TB1,

TB2). Phép phân chia này sẽ tạo ra một đỉnh mới vc ở tâm của hình thoi, và cho kết quả

là một lưới tam giác mới. Nếu tam giác T không có láng giềng đáy TB, thì chỉ có tam

giác T bị phân chia thành hai tam giác con. Phép kết hợp có thể được áp dụng cho hình

thoi (T, TB) khi tất cả các tam giác con của T và TB (nếu TB tồn tại) đều có trong lưới

tam giác. Trong trường hợp này, chúng ta nói (T, TB) là một hình thoi khả hợp

(mergeable diamond) của lưới tam giác.

Một vấn đề quan trọng về các phép phân chia và kết hợp là bất kì lưới tam giác

nào đều có thể có được từ bất kì một lưới tam giác khác thông qua một chuỗi các phép

phân chia và kết hợp.

Chúng ta có thể tạo chuyển động cho các phép phân chia và kết hợp thông qua

kỹ thuật morphing đỉnh để tạo nên tính liên tục tạm thời cho các đỉnh mới. Với khoảng

thời gian t ∈ [0, 1], giả sử có phép phân chia một hình thoi (T, TB) như trong Hình 4.2.

Thay vì di chuyển điểm vc ngay đến vị trí mới của nó wc=w(vc), mà ta cho nó di chuyển

(

)

2/))

vw (

wt )

−

dần dần trên đoạn thẳng từ trung điểm cạnh huyền lúc chưa phân chia

tw )( a

tw c

vw ( 1

- 27 -

đến vị trí mới: . Và tương tự phép kết hợp.

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.

Tam giác T không thể phân chia được khi tam giác láng giềng đáy TB ở mức thô

hơn. Để tam giác T có thể phân chia thì tam giác TB bắt buộc phải được phân chia trước,

phép phân chia này có thể kéo dài thành chuỗi đệ qui. Trong Hình 4.3 ta cần đến 4

phép phân chia. Do đó các phép phân chia ép buộc (forced splits) là cần thiết cho thuật

toán tối ưu trong phần sau.

Hình 4-3: Phép phân chia ép buộc cho tam giác T.

Lưới tam giác ban đầu gồm nhiều tam giác có thể được sử dụng để biểu diễn

một đa giác bất kì. Nếu lưới tam giác ban đầu chỉ gồm các hình thoi, thì các phép phân

chia và kết hợp có thể được sử dụng một cách tự do như trong trường hợp chỉ có một

- 28 -

tam giác gốc. Đối với địa hình, lưới tam giác thông thường là một hình thoi.

4.2 Tối ưu với hàng đợi kép

Các phép phân chia và kết hợp cung cấp một cách uyển chuyển cho việc cập

nhật lưới tam giác được tốt hơn. Chúng ta không cần quan tâm đến việc tránh các vết

nứt (cracks) hay các đỉnh có dạng T (T-vertices). Trong phần này sẽ giới thiệu một

thuật toán vét cạn dùng để vận hành quá trình phân chia và kết hợp. Ý tưởng rất đơn

giản: lưu các giá trị độ ưu tiên (priorities) cho mỗi tam giác trong lưới tam giác, bắt đầu

với lưới tam giác ban đầu (base triangulation), và thực hiện phép phân chia ép buộc lặp

đi lặp lại cho tam giác có giá trị ưu tiên cao nhất. Như vậy, tiến trình này tạo ra một

chuỗi lưới tam giác để cực tiểu hóa giá trị ưu tiên cực đại (thường là một biên lỗi –

error bound) ở mỗi bước lặp. Yêu cầu duy nhất để bảo đảm cho tính tối ưu này đó là

các giá trị độ ưu tiên phải đơn điệu (monotonic), nghĩa là giá trị ưu tiên của tam giác

con không được lớn hơn của tam giác cha. Thêm một hàng đợi ưu tiên thứ hai – cho

các hình thoi có thể kết hợp lại được – cho phép một thuật toán vét cạn có thể bắt đầu

từ một lưới tam giác tối ưu trước đó khi các giá trị độ ưu tiên thay đổi, và do đó sẽ có

ưu điểm là tận dụng được tính phụ thuộc của các ảnh với nhau.

4.2.1 Hàng đợi phân chia (split queue)

Giả sử rằng với mỗi tam giác T đều có một giá trị ưu tiên đơn điệu p(T)∈[0,1].

Khi lưới tam giác T được xây dựng từ trên xuống, chúng ta sẽ quản lý một hàng đợi ưu

tiên Qs chứa tất cả các tam giác hiện tại có trong T. Thuật toán vét cạn từ trên xuống

như sau:

Đặt T = lưới tam giác ban đầu.

Với tất cả T ∈ T, chèn T vào Qs.

Trong khi T quá nhỏ hay không chính xác {

Tìm T có giá trị ưu tiên cao nhất trong Qs.

Phân chia ép buộc cho T.

- 29 -

Cập nhật hàng đợi phân chia như sau: {

Xóa T và các tam giác phân chia khác khỏi Qs.

Thêm các tam giác mới trong T vào Qs.

}

Thuật toán vét cạn này tạo ra các lưới tam giác tối ưu tại mỗi bước lặp. Giả sử

có lưới tam giác khác T’ có giá trị ưu tiên cực đại nhỏ hơn T. Rõ ràng là T’ nhất định

chỉ chứa các con cháu của tất cả các tam giác bị ép buộc phân chia trong khi xây dựng

T. Bởi vì phép phân chia ép buộc (force-split) tạo ra các bước làm mịn cần thiết ít nhất

mà vẫn giữ được tính liên tục, nên T’ không thể chứa bất kì tổ tiên nào cả của các tam

giác trong T. Cuối cùng, bởi vì T’ có giá trị ưu tiên thấp hơn, nên nó nhất định chỉ

chứa các con cháu của ít nhất một tam giác trong T. Do đó, T’ có nhiều tam giác hơn T

và vì thế nên T là tối ưu. Tổng số các phép phân chia và kết hợp được thực hiện bởi

thuật toán từ trên-xuống (top-down algorithm) là xấp xỉ N, số lượng tam giác trong lưới

tam giác cuối cùng T.

4.2.2 Hàng đợi kết hợp (merge queue)

Bây giờ giả sử rằng cho các giá trị ưu tiên biến thiên theo thời gian pf(T)∈[0,1]

cho mỗi frame f ∈ (0, 1, …), và bài toán là xây dựng các lưới tam giác tối ưu (T0, T1,

…). Nếu các giá trị ưu tiên này thay đổi từ từ, thì các lưới tam giác tối ưu ứng với bất

kỳ hai frame kế tiếp nhau sẽ tương tự với một frame khác. Trong trường hợp này, việc

hiển thị (performance) sẽ được cải thiện nếu chúng ta sử dụng lưới tam giác Tf – 1 làm

điểm bắt đầu để xây dựng lưới tam giác Tf. Điều này được thực hiện bằng cách quản lý

hàng đợi ưu tiên thứ hai Qm, chứa tất cả các hình thoi khả hợp trong lưới tam giác hiện

tại. Giá trị ưu tiên cho hình thoi khả hợp (T, TB) được đặt bằng giá trị ưu tiên lớn hơn

- 30 -

của hai tam giác đó, max{pf(T),pf(TB)}. Thuật toán vét cạn này như sau:

Nếu f = 0 {

Đặt T = lưới tam giác ban đầu.

Xóa Qs, Qm.

Tính các giá trị ưu tiên cho các tam giác và các hình thoi của T, sau đó

chèn vào Qs, Qm tương ứng.

} ngược lại {

Tiếp tục T = Tf – 1.

Cập nhật giá trị ưu tiên cho các phần tử của Qs, Qm.

}

Trong khi T không đạt độ chính xác / kích thước mong muốn, hay giá trị ưu tiên

phân chia lớn nhất lớn hơn giá trị ưu tiên kết hợp nhỏ nhất {

Nếu T quá lớn hay quá chi tiết {

Tìm giá trị ưu tiên thấp nhất (T, TB) trong Qm.

Kết hợp (T, TB).

Cập nhật các hàng đợi như sau: {

Xóa tất cả tam giác con đã được kết hợp lại khỏi Qs.

Thêm các tam giác cha kết hợp T, TB vào Qs.

Xóa (T, TB) khỏi Qm.

Thêm tất cả hình thoi khả hợp mới vào Qm.

}

} ngược lại {

Tìm giá trị ưu tiên cao nhất T trong Qs.

Phân chia ép buộc cho T.

Cập nhật các hàng đợi như sau: {

Xóa T và các tam giác phân chia khác khỏi Qs.

Thêm các tam giác mới trong T vào Qs.

- 31 -

Xóa khỏi Qm các hình thoi đã được phân chia.

Thêm các hình thoi khả hợp mới vào Qm.

}

Đặt Tf = T.

Thuật toán vét cạn này tạo ra lưới tam giác Tf có cùng giá trị ưu tiên như thuật

toán từ trên-xuống được thực hiện trên lưới tam giác ban đầu. Tổng quát thuật toán này

không tạo ra các lưới tam giác tối ưu trong các bước lặp trung gian (ví dụ, Tf – 1 thường

không tối ưu với frame f), nhưng nó sẽ đạt tối ưu nếu sử dụng ít nhất các phép phân

chia và kết hợp cho Tf – 1. Tổng số các phép phân chia và kết hợp xấp xỉ bằng ∆N, được

định nghĩa như là số tam giác không có chung của Tf và Tf – 1. Trong trường xấu nhất,

∆N có thể là Nf – 1 + Nf. Trường hợp như thế này ta có thể dễ dàng thấy được: có số

lượng lớn tam giác và hình thoi mà các giá trị ưu tiên nằm giữa giá trị ưu tiên kết hợp

cực tiểu và giá trị ưu tiên phân chia cực đại. Biện pháp khắc phục trong trường hợp này

là quay trở về với thuật toán từ trên-xuống (top-down algorithm), nó có thể được thực

hiện bằng cách khởi tạo T, Qs và Qm thông qua f = 0.

4.3 Các khái niệm lỗi (error metrics)

Trong phần này mô tả các đại lượng lỗi và các biên lỗi được sử dụng để tính

toán các giá trị ưu tiên cho các hàng đợi. Đặc biệt chúng ta giả sử rằng ánh xạ từ đỉnh

(vertex) sang không gian thế giới (world-space) w(v) có dạng w(v)=(vx,vy,z(v)), trong

đó (vx, vy) là tọa độ của đỉnh v, và z(v) là chiều cao tại v. Chúng ta đặt bản đồ chiều cao

cho tam giác T là zT(x, y). Chúng ta cũng giả sử hệ thống tọa độ camera và phép chiếu

- 32 -

phối cảnh được cho sẵn trong mỗi frame.

4.3.1 Các biên xếp chồng trong không gian thế giới

Với lưới tam giác, đường biên thuận tiện cho mỗi tam giác T là biên nêm

(wedgie), được định nghĩa là một hình khối chứa các điểm (x, y, z) trong đó (x,y)∈T và

|z – zT(x, y)| ≤ eT với độ dày nêm eT ≥ 0. Chúng ta xem đoạn thẳng từ (x,y,z – eT) đến (x,

y, z + eT) là đoạn độ dày (thickness segment) cho v. Các biên nêm xếp chồng được xây

dựng từ dưới-lên, bắt đầu với eT = 0 cho tất cả T ở mức mịn nhất lmax. Độ dày nêm eT

cho tam giác cha được định nghĩa theo các độ dày nêm của các tam giác con eT0 và eT1.

vz (

)

(

|} +

−

Các biên nêm xếp chồng kín nhất được cho bởi công thức:

e T

e max{ T 0

e T 1

(

)

2/))

vz ((

(1)

vz ( 1

. Chú ý rằng phép tính này nhanh và cục bộ, tạo điều Trong đó

kiện thuận lợi cho địa hình động. Hình 4.4 biểu diễn các nêm xếp chồng phụ thuộc vào

đỉnh v.

Hình 4-4: Các nêm xếp chồng cho miền 1-D phụ thuộc vào v.

4.3.2 Sự méo mó hình học

Với lưới tam giác được phủ texture, sự méo mó hình học trong không gian màn

hình khác với sự méo mó màu sắc. Chúng ta giả sử các màu sắc cho các điểm trên bề

mặt được thể hiện chính xác như màu sắc trong hình texture. Các lỗi hình ảnh còn lại

- 33 -

có thể được thể hiện đơn thuần như là sự méo mó hình học: khoảng cách giữa nơi mà

mỗi điểm bề mặt nên đặt trên màn hình và nơi mà lưới tam giác đặt điểm đó. Thông

qua toàn bộ ảnh chúng ta tính toán độ chênh lệch cực đại theo các điểm đó. Đây là khái

niệm lỗi cơ bản của ROAM.

Đặt s(v) là vị trí chính xác cho điểm v trên màn hình và sT(v) là vị trí xấp xỉ từ

lưới tam giác T. Chúng ta định nghĩa độ chênh lệch hình học theo điểm (pointwise

geometric distortion) ở v là dist(v) = ||s(v) – sT(v)||2. Với toàn bộ ảnh, chúng ta định

nghĩa độ chênh lệch cực đại là distmax = maxv∈Vdist(v) trong đó V là tập hợp các điểm v

có vị trí trong không gian thế giới w(v) nằm trong khung nhìn (view frustum).

Trong thực tế, biên trên (upper bound) được tính bằng độ chênh lệch cực đại.

Với mỗi tam giác T trong lưới tam giác, một biên trên cục bộ (local upper bound) theo

độ chênh lệch được xác định bằng cách chiếu nêm của T lên màn hình, được mô tả

trong Hình 4.5. Biên được định nghĩa là chiều dài cực đại của các đoạn độ dày sau khi

chiếu với tất cả v ∈ T. Các biên cục bộ này là đơn điệu, và sẽ được sử dụng để tạo

thành các giá trị ưu tiên trong hàng đợi. Nếu một nêm mở rộng phía sau mặt phẳng cắt

ở gần, thì độ ưu tiên của tam giác được đặt là giá trị cực đại và việc tính toán biên

- 34 -

chênh lệch được bỏ qua.

Hình 4-5: Biên chênh lệch bởi việc chiếu nêm lên màn hình.

Bởi tính chất riêng biệt của phép chiếu phối cảnh, độ dày nêm đã chiếu cực đại

không phải luôn luôn xảy ra ở một trong các đỉnh tam giác. Điều này dẫn đến việc tính

toán biên trên sau. Đặt (p, q, r) là tọa độ của điểm w(v) trong không gian camera mà

không có chiếu phối cảnh, và không mất đi tính tổng quát, giả sử phép chiếu phối cảnh

có dạng s = (p/r, q/r). Sự chênh lệch không gian màn hình ở v∈T được giới hạn bởi

việc chiếu đoạn độ dày ở v. Đặt (a, b, c) là vectơ không gian camera tương ứng với

vectơ độ dày trong không gian thế giới (0, 0, eT). Độ chênh lệch ở được giới hạn bởi:

(2)

Có thể được viết lại:

(3)

Ta thấy giá trị cực tiểu của r2 – c2 và giá trị cực đại của (ar-cp)2 + (br-cp)2 xảy

ra ở các đỉnh góc của T (mặc dù tổng quát không có cùng góc). Do đó biên trên theo

- 35 -

dist(v) có thể xác định bằng cách thay các giá trị cực đại và cực tiểu vào biểu thức 3.

4.3.3 Hiệu chỉnh Line-of-site (LOS)

Đến đây, giá trị độ ưu tiên của các phần tử trong hàng đợi được tính toán từ

khoảng chênh lệch trên màn hình đối với tam giác T. Giá trị ưu tiên này có thể được

biến đổi để bảo đảm rằng các LOS đã chọn có bị che khuất hay không. Một phương

pháp đơn giản để thực hiện điều này là chúng ta thay đổi giá trị độ ưu tiên cho các tam

giác có nêm giao với LOS. Bằng cách thiết lập các giá trị ưu tiên bằng một giá trị cực

đại mà chúng ta qui định trước, thì các phép phân chia sẽ được ưu tiên thực hiện hơn

đủ để đảm bảo rằng các tam giác có thể được nhìn thấy một cách chính xác dọc theo

đường LOS. Phương pháp này có khuynh hướng gia tăng các phép phân chia hơn mức

cần thiết, mặc dù sự vượt mức này thực tế thường là nhỏ so với tổng số toàn bộ các tam

giác.

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.

4.3.4 Các khái niệm khác

Sau đây là một vài sự biến đổi giá trị độ ưu tiên mà ta có thể áp dụng cho

- 36 -

ROAM.

• Giảm độ chi tiết cho mặt khuất: giá trị độ ưu tiên có thể được đặt bằng

giá trị cực tiểu cho các tam giác mà các tam giác trong nhánh tam giác

này đều là mặt khuất.

• Sự chênh lệch theo phương pháp tuyến: đối với quan điểm được quyết

định bằng các véctơ được nội suy từ các đỉnh, giá trị độ ưu tiên nên được

đặt cho các tam giác có sự chênh lệch pháp tuyến lớn.

• Sự chênh lệch tọa độ texture: đối với các ánh xạ từ bề mặt sang tọa độ

texture, giá trị độ ưu tiên nên được thêm vào tương ứng với độ lớn của sự

chênh lệch vị trí trong không gian màn hình kết hợp với việc xấp xỉ tọa

độ texture.

• Các cạnh Silhouette: chúng ta có thể nhấn mạnh những tam giác có

đường biên pháp tuyến chuyển từ mặt khuất sang mặt nhìn thấy được.

• View frustum: các niêm tam giác nằm bên ngoài sáu mặt phẳng cắt có

thể được đặt bằng giá trị độ ưu tiên cực tiểu.

• Sự mờ không khí: giá trị độ ưu tiên có thể giảm đi nếu sương mù làm

giảm tầm nhìn.

• Bố trí đối tượng: để bố trí chính xác các đối tượng trong địa hình, giá trị

ưu tiên của các tam giác dưới mỗi đối tượng có thể tăng dần theo như

chúng ta qui định.

4.4 Cải tiến quá trình hiển thị

Chúng ta mô tả các cải tiến để thuật toán ROAM có thể thực hiện ở tốc độ cao

đối với các lưới tam giác có hàng ngàn tam giác.

4.4.1 View-frustum culling

View frustum được định nghĩa là phần không gian được giới hạn bởi sáu mặt

- 37 -

phẳng. Mỗi tam giác trong cây nhị phân (toàn bộ lưới tam giác) được đặt một cờ IN

cho mỗi sáu nữa không gian (halfspace), và một nhãn tổng hợp OUT, ALL-IN hay

DONT-KNOWN, được định nghĩa như sau: IN được đặt khi nêm tam giác hoàn toàn

nằm bên trong nữa không gian, OUT được đặt khi nêm tam giác hoàn toàn nằm bên

ngoài ít nhất một halfspace, ALL-IN được đặt nếu tất cả cờ IN được đặt, và DONT-

KNOWN được đặt nếu không phải OUT hay ALL-IN.

Từ một frame này chuyển sang một frame khác, chúng ta phải cập nhật lại cờ và

nhãn cho các tam giác, việc này được xử lý bằng cách duyệt đệ qui cây nhị phân tam

giác. Nếu tam giác T có nhãn OUT hay ALL-IN ở frame trước, và các nhãn này đúng

với frame hiện tại, thì cây con của tam giác T không cần phải cập nhật lại và quá trình

đệ qui dừng lại. Mặt khác, T kế thừa các cờ IN từ tam giác cha và kiểm tra lại nêm tam

giác của nó với các halfspace không đánh dấu IN, đặt cờ IN mới cho thích hợp. Nếu

nêm tam giác hoàn toàn ở ngoài bất kì halfspace nào, T và tất cả tam giác con được đặt

là OUT. Nếu tất cả cờ IN được đặt, T và tất cả tam giác con được đặt ALL-IN. Mặt

khác T được đặt là DONT-KNOWN và tiếp tục quá trình đệ qui cho các tam giác con.

4.4.2 T-stripping

Tốc độ hiển thị có thể tăng lên nếu chúng ta tổ chức các tam giác thành các

strips, nhưng để tối ưu thì lại là một vấn đề khó. Chúng ta chỉ giả sử rằng các strip

không tổng quát (không có “hoán chuyển các đỉnh với nhau”). Chúng ta sử dụng

phương pháp cải tiến đơn giản chỉ có được chiều dài trung bình của strip từ 4 – 5 tam

giác. Khi các tam giác bị phân chia, kết hợp hay thay đổi trạng thái view-culling, thì

thực hiện liên kết strip. Việc xóa một tam giác ra khỏi strip sẽ dẫn đến strip này sẽ bị

xóa đi, hoặc bị ngắn lại nếu tam giác đó ở cuối strip, hay bị phân làm hai.

4.4.3 Trì hoãn việc tính toán lại độ ưu tiên

Các giá trị ưu tiên về độ chênh lệch trên màn hình của các tam giác thay đổi nếu

- 38 -

như vị trí hiển thị thay đổi, thường thì chậm và trơn. Việc tính toán lại độ ưu tiên của

tất cả các tam giác cho mỗi frame là rất tốn kém. Thay vào đó, giá trị ưu tiên sẽ chỉ

được tính toán lại khi chúng ảnh hưởng đến quyết định phân chia hay kết hợp.

Cho một giới hạn tốc độ trên điểm nhìn (viewpoint), các giới hạn có thể có được

cho các giá trị ưu tiên về độ chênh lệch trên màn hình theo thời gian. Vì thế độ ưu tiên

trực giao (được định nghĩa là độ ưu tiên của hàng đợi phân chia khi quá trình phân chia

hay kết hợp hoàn tất) thay đổi dần dần từ frame này sang frame khác (thường thay đổi

khoảng 1%). Việc tính toán lại các giá trị cho một tam giác có thể được hoãn lại cho

đến khi độ ưu tiên trực giao nằm trong khoảng giá trị ưu tiên. Danh sách trì hoãn được

lưu lại cho mỗi một vài tá frame kế tiếp. Chỉ những tam giác trong danh sách trì hoãn

của frame hiện tại mới được tính toán lại giá trị ưu tiên. Nếu có đủ thời gian, các tam

giác có thể được tính toán lại bằng chuỗi các danh sách trì hoãn. Sau khi quá trình tính

toán lại xong, tam giác được đặt vào danh sách trì hoãn, điều này sẽ cung cấp một thời

khóa biểu cho quá trình tính toán lại này.

4.4.4 Tối ưu lũy tiến (progressive optimazation)

Để đảm bảo cho tốc độ hiển thị, việc tối ưu quá trình lập lưới tam giác nên dừng

lại khi khoảng thời gian đã thiết lập sắp hết. Thuật toán ROAM có hỗ trỡ điều này bởi

vì việc cập nhật quá trình tối ưu và stripping thực hiện đối với một phép phân chia hay

kết hợp kế tiếp nhau. Dĩ nhiên là nếu dừng lại sớm sẽ dẫn đến việc lập lưới tam giác

không tối ưu. Tuy nhiên, bởi vì các bước phân chia và kết hợp được thực hiện theo thứ

tự giảm dần của độ quan trọng, việc thực hiện một phần có thể tối ưu theo trực quan

khi chúng ta đạt gần đến tối ưu thực trong khoảng thời gian cho phép trong khi vẫn

quản lý được số lượng tam giác mong muốn. Qui trình này gọi là tối ưu lũy tiến. Việc

tính toán lại giá trị ưu tiên cũng có thể được giới hạn lại theo thời gian cho trước. Chỉ

có một công đoạn của ROAM không thể thực hiện được như trên đó là view-frustum

culling, nhưng may mắn là nó chỉ đòi hỏi một khoảng thời gian rất ít và được hoàn

- 39 -

thành trước quá trình tính toán lại giá trị ưu tiên và quá trình tối ưu lưới tam giác.

4.5 Ưu điểm và khuyết điểm

4.5.1 Ưu điểm

Thuật toán ROAM được sử dụng rất rộng rãi trong các ứng dụng liên quan đến

địa hình phụ thuộc vào tính hiển thị cao.

• ROAM là một thuật toán tham lam nhằm đạt đến lưới tam giác tối ưu

trong khi sử dụng một số lượng ít nhất các phép phân chia và kết hợp nếu

có thể được.

• Thuật toán này rất đơn giản và dễ hiểu và cũng dễ cài đặt.

• Việc chọn cấu trúc biểu diễn lưới điểm và các thao tác trên đỉnh không

làm xảy ra hiện tượng T-vertices, do đó không cần phải có biện pháp gì

để tránh hiện tượng này.

• Vì các hàng đợi ưu tiên đều được sắp xếp theo thứ tự nên ta có thể trực

tiếp có được số lượng tam giác của lưới tam giác cuối cùng.

• Với các ứng dụng yêu cầu tính toán đường ngắm (line of sight) trực tiếp,

ROAM có thể bảo đảm rằng giá trị ưu tiên lớn nhất chỉ ra được các

đường ngắm.

• ROAM có hỗ trợ việc lập lưới tam giác động (tính cố kết frame – frame

coherency) để cải thiện tốc độ hiển thị.

• Có rất nhiều cải tiến quá trình hiển thị bằng các khái niệm lỗi và những

thao tác phục vụ cho ROAM, bao gồm việc tối ưu đường ngắm.

4.5.2 Khuyết điểm

Chỉ có một số ít khuyết điểm cho thuật toán ROAM này.

• Yêu cầu dung lượng bộ nhớ cho mỗi đỉnh là rất tốn kém so với một số

- 40 -

hướng khác như thuật toán của Röttger.

• Cấu trúc biểu diễn cho lưới tam giác trong ROAM tự nó không hỗ trợ tốt

cho biểu diễn đỉnh như dãy tam giác (triangle-strip), do đó sẽ dẫn đến

- 41 -

làm giảm tốc độ hiển thị.

Chương 5

Thuật toán Diamond

Thuật toán này được Henri Hakl đưa ra vào năm 2001, đây là một cải tiến của

thuật toán ROAM. Thuật toán này sử dụng cấu trúc biểu diễn lưới điểm là cây tứ phân

tam giác thay thế cây nhị phân tam giác trong ROAM, với cấu trúc này có thể phân ly

thành các dãy tam giác (triangle-strip) một cách tự nhiên. Thay vì 2 hàng đợi như

ROAM, thuật toán này bỏ qua hàng đợi ưu tiên mà sử dụng 4 hàng đợi LIFO có hỗ trợ

việc chèn và xóa theo thời gian cố định.

5.1 Biểu diễn

5.1.1 Cây tứ phân tam giác (triangle quadtree)

Bất kì một tam giác nào đều có thể thõa mãn là gốc cho một cây tứ phân tam

giác và tam giác con của tam giác này sẽ có hình dạng như tam giác gốc. Với các mục

- 42 -

đích này mà không làm mất đi tính tổng quát, chúng ta sẽ giả sử gốc tam giác đều.

Hình 5-1: Vài mức ban đầu của cây tứ phân tam giác.

Từ biểu diễn cây tứ phân tam giác này, ta có được hai kiểu tam giác, tam giác

hướng lên và tam giác hướng xuống. Thuật toán CLOD mà chúng ta sẽ thực hiện các

hàm không phụ thuộc vào hướng của tam giác, tuy nhiên trong quá trình hiển thị thì

việc phân biệt các tam giác đó là quan trọng vì nó sẽ hổ trợ cho việc khử mặt khuất.

Để giúp đỡ cho việc thực hiện thuật toán, trước tiên chúng ta định nghĩa một

tam giác và các mối quan hệ của nó như sau (Hình 5.2):

• 3 đỉnh v1, v2, v3 được định nghĩa từ trái sang phải.

• 3 láng giềng n1, n2, n3 được định nghĩa từ trái sang phải.

• 4 tam giác con a, b, c, d – a luôn là tam giác con ở giữa, các tam giác con

- 43 -

còn lại được định nghĩa từ trái sang phải.

Hình 5-2: Định nghĩa tam giác và các mối quan hệ của nó.

Chúng ta định nghĩa phép phân chia và kết hợp thông qua biểu diễn lưới điểm

như sau: phép phân chia sẽ thay thế một tam giác bằng 4 tam giác con, phép kết hợp là

phép đảo của phép phân chia. Hình 3 mô tả các phép toán này.

- 44 -

Hình 5-3: Phép phân chia và kết hợp.

5.1.2 Các đặc tính

Như đã đề cập ở trên, cây tứ phân tam giác cung cấp các tính năng giống như

cây nhị phân tam giác. Tuy nhiên, cây tứ phân tam giác có một số đặc tính khác với

cây nhị phân tam giác và nó làm tăng tính hiện thực và khả năng hiển thị tốt hơn.

Trong cách biểu diễn cây nhị phân tam giác, một đỉnh đã cho có thể được chia

sẽ bởi từ 4 đến 8 tam giác, trong khi đó với cách biểu diễn cây tứ phân tam giác, thì

mỗi đỉnh chỉ luôn được chia sẽ bởi 6 tam giác. Do đó trong biểu diễn cây tứ phân tam

giác, một phần tử được hiển thị luôn luôn gồm 6 tam giác cho mỗi đỉnh. Tính cố định

này sẽ làm cho việc hiển thị chính xác hơn. Thêm vào đó hiện tượng vertex-popping

cũng được giảm bớt, chẳng hạn như loại bỏ được trường hợp các đỉnh được chia sẽ bởi

4 tam giác trong một khung hình và bởi 8 tam giác trong khung hình kế tiếp.

Có lẽ quan trọng hơn là lưới tam giác có được từ một cây tứ phân tam giác có

phù với việc tối ưu trong hiển thị như là việc sử dụng các dãy tam giác (triangle-strips)

chẳng hạn. Các dãy tam giác trong tổ chức cây nhị phân tam giác có được bằng cách

lưu trong một hằng số và thường rất ngắn khoảng trung bình từ 4 – 5 tam giác mỗi dãy

(phụ thuộc vào kích thước địa hình và mức độ chi tiết hiển thị), và các cấu trúc hình

học phụ không phù hợp lắm với các dãy tam giác dài. Ngược lại, cây tứ phân tam giác

vốn có thể phân tích thành các dãy tam giác dài và thuận tiện cho phần cứng trong quá

trình tạo lưới tam giác. Chiều dài trung bình của dãy tam giác phụ thuộc vào mức độ

chi tiết hiển thị (rendering detail), kích thước địa hình, và sai số địa hình (terrain

variance).

5.1.3 Tính liên tục (continuity) của lưới tam giác

Với biểu diễn lưới tam giác này không được hoàn chỉnh, nó thất bại ở tính liên

tục của lưới tam giác: trong lưới tam giác có các đỉnh dạng T (T-vertices) giữa các tam

giác láng giềng ở các mức khác nhau. Hình 5.4 bên dưới là một ví dụ về tính không

- 45 -

liên tục của lưới tam giác.

Hình 5-4: Tính không liên tục của lưới tam giác.

Vấn đề này dễ dàng được khắc phục: thực hiện lập lưới tam giác nếu các phép

phân chia và kết hợp không tạo ra tính không liên tục trong lưới tam giác; chỉ cần xem

xét đến mức độ chi tiết (level) của tam giác ở trong bước này. Trong suốt quá trình

phát sinh lưới tam giác, hiện tượng T-vertices được loại bỏ bằng cách xem xét đến các

láng giềng rồi có các thao tác đặc biệt tương ứng, như mô tả trong hình 5.5 bên dưới.

Hình 5-5: Hiệu chỉnh lại tính không liên tục cho lưới tam giác.

5.2 Thuật toán Diamond

Trong phần này, chúng ta sẽ mô tả thuật toán hiển thị địa hình như đã đề cập ở

trên. Trước tiên, chúng ta sẽ mô tả 4 hàng đợi LIFO vận hành quá trình lập lưới tam

giác cho địa hình; sau đó chúng ta đưa ra mô tả đến các phép phân chia và kết hợp

cùng với vòng lặp hiển thị chính của thuật toán. Cuối cùng chúng ta sẽ điểm mạnh và

- 46 -

yếu của thuật toán này.

5.2.1 Các hàng đợi tam giác

Thuật toán ROAM sử dụng hai hàng đợi: các hàng đợi ưu tiên chứa đựng tất cả

các tam giác khả phân và khả hợp, được sắp xếp theo thứ tự của giá trị ưu tiên. Các

hàng đợi ưu tiên được quản lý cùng với các thao tác mà thuật toán ROAM thực hiện,

điều này cho phép thuật toán có thể trực tiếp đạt được số lượng tam giác cho trước: có

thể chỉ ra rằng trong một khung hình nào đó thì nên gồm có, ví dụ, 3000 tam giác. Sau

đó thuật toán sẽ thực hiện phép phân chia và kết hợp các tam giác cho đến khi lưới tam

giác đạt đến số tam giác là 3000 tam giác. Phụ thuộc vào các hàng đợi ưu tiên, mỗi

thao tác phân chia hay kết hợp là tối ưu mang tính cục bộ, cho kết quả là một lưới tam

giác tối ưu với bất kỳ số lượng tam giác nào.

Một vài năm trở lại đây, mục đích quản lý số lượng tam giác cố định là để bảo

đảm một ứng dụng có thể chạy ở một tốc độ hiển thị cố định, từ đó nhu cầu xử lý từ

khung hình này đến khung hình khác gần như là như nhau đối với số tam giác không

đổi. Tuy nhiên phần cứng đồ họa ngày càng mạnh và đặc biệt là khả năng phần cứng

hổ trợ xử lý các phép biến đổi và chiếu sáng, nên có thể loại bỏ được nhu cầu quản lý

số lượng tam giác cố định để có được tốc độ hiển thị không đổi. Các phần cứng đồ họa

hiện đại có thể dễ dàng đương đầu với cả ngàn tam giác mà tốc độ hiển thị hầu như

không bị ảnh hưởng.

Từ khi tốc độ hiển thị ngày càng không phụ thuộc vào số lượng tam giác thì các

hàng đợi ưu tiên đã được sắp xếp không còn là điều kiện tiên quyết cho quá trình lập

lưới tam giác cho địa hình. Thay vào đó thuật toán sẽ sử dụng 4 hàng đợi LIFO có thời

gian thêm vào và xóa đi không thay đổi.

• SplitBelow – chứa tất cả tam giác khả phân có giá trị ưu tiên bé hơn giá

trị ưu tiên đích.

• SplitAbove – chứa tất cả tam giác khả phân có giá trị ưu tiên lớn hơn giá

- 47 -

trị ưu tiên đích.

• MergeBelow – chứa tất cả tam giác khả hợp có giá trị ưu tiên bé hơn giá

trị ưu tiên đích.

• MergeAbove – chứa tất cả tam giác khả hợp có giá trị ưu tiên lớn hơn giá

trị ưu tiên đích.

5.2.2 Thuật toán

Trong phần này chúng ta sẽ đi vào mô tả chi tiết thuật toán địa hình Diamond

(Diamond terrain algorithm). Trước tiên chúng ta xem xét vòng lặp chính của thuật

toán, sau đó mô tả chi tiết các phép phân chia (và qui trình phát sinh các tam giác con)

và các phép kết hợp.

A. Vòng lặp chính:

Vòng lặp hiển thị của thuật toán này bao gồm 2 quá trình phân biệt: quá trình

đánh giá độ ưu tiên và quá trình lặp lưới tam giác. Trong quá trình đánh giá độ ưu tiên,

giá trị ưu tiên của tất cả các tam giác trong các hàng đợi đều được đánh tính toán lại và

các tam giác đó có thể được đưa vào hàng đợi nếu cần thiết. Trong quá trình lặp lưới

tam giác, tất cả các tam giác khả hợp có độ ưu tiên nhỏ hơn độ ưu tiên đích sẽ được kết

hợp lại và tất cả các tam giác khả phân lớn hơn độ ưu tiên đích sẽ được phân chia.

Nếu ResetDiamond thì

Thiết lặp lại lưới tam giác và hàng đợi.

Lọc (cull) và dành ưu tiên cho các tam giác láng giềng đáy đầu tiên và

xếp các tam giác vào hàng đợi nào thích hợp SplitAbove hay

SplitBelow.

Ngược lại

Duyệt qua hàng đợi SplitBelow, đánh giá lại độ ưu tiên và sắp xếp lại

- 48 -

các phần tử vào hàng đợi SplitAbove nếu cần thiết.

Duyệt qua hàng đợi MergeAbove, đánh giá lại độ ưu tiên và sắp xếp lại

các phần tử vào hàng đợi MergeBelow nếu cần thiết.

Trong khi MergeBelow chưa rỗng,

Kết hợp các phần tử trong MergeBelow.

Trong khi SplitAbove chưa rỗng,

Phân chia các phần tử trong SplitAbove.

ResetDiamond là một giá trị nhị phân, nếu là đúng (true) vòng lặp chạy lần đầu

tiên. Nếu ResetDiamond = true với mỗi khung hình phía sau, thì thuật toán chỉ thực

hiện các phép phân chia trên lưới tam giác; còn nếu là false thì thuật toán sẽ là động

(phụ thuộc vào khung hình) và sẽ thực hiện cả hai phép phân chia và kết hợp.

Chú ý rằng sau mỗi lần thực hiện xong vòng lặp này, hàng đợi MergeBelow và

SplitAbove sẽ trở nên rỗng – tất cả các tam giác khả hợp và khả phân đều nằm trong

hàng đợi SplitBelow và MergeAbove sau mỗi lần lặp.

B. Phép phân chia:

Về mặt hình học, phép phân chia khá đơn giản và được thực hiện dễ dàng, tuy

nhiên, nó vô cùng quan trọng đối với quá trình thực hiện của thuật toán mà bốn hàng

đợi LIFO được quản lý một cách chính xác.

Phép phân chia cũng đảm bảo rằng các tam giác láng giềng chỉ chênh lệch nhau

một mức (level). Điều này được thực hiện bằng cách ép buộc tam giác láng giềng phân

chia nếu nó quá thô, để tam giác đang xét có thể phân chia được.

Nếu tam giác đang xét đã được đưa vào hàng đợi

Lấy tam giác đó ra khỏi hàng đợi SplitAbove.

Nếu tam giác cha đã được đưa vào hàng đợi

- 49 -

Lấy tam giác đó ra khỏi hàng đợi kết hợp.

Nếu tam giác láng giềng thô hơn tam giác đang xét

Phân chia tam giác láng giềng.

Nếu tam giác cha của tam giác láng giềng đã được đưa vào hàng đợi

Lấy tam giác đó ra khỏi hàng đợi kết hợp.

Tạo ra các tam giác con từ tam giác đang xét.

Lọc (cull) và dành ưu tiên cho các tam giác con và đưa vào hàng đợi SplitAbove

hay SplitBelow cho phù hợp.

Nếu tam giác đang xét là khả hợp

Đưa nó vào hàng đợi MergeAbove.

Chú ý rằng một tam giác khả hợp nếu nó có tam giác con nhưng không có tam

giác cháu.

C. Quá trình phát sinh tam giác con:

Quá trình phát sinh tam giác con là một phần của phép phân chia tam giác. Khi

thực hiện quá trình phát sinh tam giác, điều quan trọng là phải chắc chắn rằng các tam

giác láng giềng phải được liên kết chính xác với nhau.

Tạo ra các tam giác con và liên kết chúng với tam giác đang xét.

Gán các tọa độ cho các tam giác con.

Nếu không có tam giác láng giềng

Thiết lặp các láng giềng là rỗng (NULL).

Ngược lại

Nếu tam giác láng giềng có con

Liên kết các tam giác con của tam giác đang xét và tam giác láng

- 50 -

giềng với nhau.

Ngược lại

Liên kết các tam giác con của tam giác đang xét với tam giác láng

giềng.

D. Phép kết hợp:

Tương tự phép phân chia, phép kết hợp thì đơn giản về mặt hình học, tuy nhiên,

việc quản lý hàng đợi cho chính xác đòi hỏi cần phải chú ý đặc biệt.

Nếu các tam giác con đã được đưa vào hàng đợi

Lấy chúng ra khỏi hàng đợi phân chia.

Lấy tam giác đang xét ra khỏi hàng đợi MergeBelow.

Chỉnh lại các liên kết cho các tam giác con của láng giềng nếu cần thiết.

Xóa các tam giác con của tam giác đang xét.

Nếu tam giác cha của láng giềng có thể kết hợp

Đưa tam giác cha vào hàng đợi kết hợp phù hợp.

Nếu tam giác cha của tam giác đang đang xét có thể kết hợp

Đưa tam giác cha vào hàng đợi kết hợp phù hợp.

Đưa tam giác đang xét vào hàng đợi SplitBelow.

5.3 Ưu và khuyết điểm

Thuật toán này dựa theo ý tưởng của ROAM nên kế thừa được các ưu điểm của

ROAM. Trong khi đó với cấu trúc biểu diễn lưới tam giác, chúng ta không cần thực

hiện một phương pháp phức tạp nào để lấy ra các strip tam giác từ lưới tam giác, mà

cấu trúc này tự nó có được các strip tam giác dài nên sẽ giảm thời gian hiển thị. Thuật

toán này sử dụng 4 hàng đợi LIFO cho phép sử dụng hiệu quả các tài nguyên trong quá

- 51 -

trình xử lý.

Chương 6

Tổng kết

Chúng em đã thực hiện cài đặt thử nghiệm các thuật toán đã nêu. Chương trình cài đặt bằng ngôn ngữ Visual C++® 6.0 và thư viện đồ họa OpenGL chạy trên nền Windows® XP trên hệ thống Pentum®IV 256M RAM và VGA 64M.

- 52 -

Hình 6-1: Địa hình được hiển thị bằng thuật toán của Röttger.

- 53 -

Hình 6-2 : Địa hình được hiển thị bằng thuật toán ROAM.

- 54 -

Hình 6-3 : Địa hình được hiển thị bằng thuật toán Diamond.

Hình 6-4 : Địa hình khi được phủ texture.

Tốc độ trung bình của các thuật toán khi hiển thị 5000 tam giác.

- 55 -

Thuật toán Röttger ROAM Diamond Tốc độ (frame/s) 84.3 63.7 75.8