7
hợp hỗn ñộn các ñiểm ñã thu thập ñược. Thuật toán tam giác hoá có
thể trình bày trong [4], [10], [11]:
2.3 Các lược ñồ xây dựng bề mặt lưới 3D
Cho V là tập hữu hạn các ñỉnh trên mặt phẳng R2 [3]. Cho E
là tập các cạnh mà các ñiểm ñầu cuối là các ñỉnh thuộc tập V. Ta có
các ñịnh nghĩa sau:
Định nghĩa 1. Lưới tam giác T = (V,E) là một ñồ thị phẳng
mà mỗi cạnh không chứa ñỉnh nào khác ngoài hai ñỉnh ñầu cuối của
nó, không có hai cạnh nào cắt nhau và tất cả các mặt là những tam
giác với hội của chúng là bao lồi của tập ñỉnh V.
Định nghĩa 2. Bài toán nối các ñiểm cho trước trên mặt
phẳng bằng các ñoạn thẳng không cắt nhau ñể tạo thành lưới tam giác
gọi là bài toán xây dựng lưới tam giác. Về mặt bản chất, bài toán xây
dựng lưới tam giác từ tập ñiểm cho trước là không duy nhất. Một
trong các ñiều kiện xây dựng lưới tam giác hay ñược sử dụng trong
các ứng dụng là ñiều kiện Delaunay.
Định nghĩa 3. Ta nói rằng lưới tam giác thỏa ñiều kiện
Delaunay nếu bên trong ñường tròn ngoại tiếp của mỗi tam giác
không chứa bất kỳ ñiểm nào thuộc lưới tam giác ñó.
2.3.1 Sơ ñồ Voronoi
Sơ ñồ Voronoi biểu diễn như sau: mỗi vùng Voronoi V(pi) là
ña giác lồi, với V(pi) là không ñóng kín nếu pi thuộc bao lồi của tập
ñiểm. Nếu v là ñỉnh của Voronoi ở ñiểm giao nhau của V(p1), V(p2)
và V(p3) thì v là tâm của ñường tròn C(v) xác ñịnh bởi p1, p2, p3.
Trong ñó C(v) là ñường tròn ngoại tiếp tam giác Delaunay tương
ứng với v. Bên trong C(v) không chứa ñiểm pj. Nếu pj là ñiểm gần
nhất ñến pj thì (pj,pj) là cạnh tam giác Delaunay. Bất kì một ñường
8
tròn nào ñi qua hai ñiểm pj,pj mà không chứa bất kỳ ñiểm nào thì
(pj,pj) là cạnh tam giác Delaunay [7], [8], [9].
2.3.2 Sơ ñồ Delaunay
Với D(P) là các ñường thẳng ñối ngẫu của V(P). Mỗi tam
giác của D(P) tương ứng ñến ñỉnh của V(P). Mỗi cạnh của D(P)
tương ứng ñến cạnh của V(P). Mỗi nút của D(P) tương ứng ñến vùng
của V(P). Đường bao của D(P) là bao lồi của P. Bên trong tam giác
của D(P) là bao lồi của P.
Phép chia nhỏ tạo ra số tam giác lớn nhất không tồn tại một
cạnh nào nối hai ñiểm có thể thêm vào mà không phá vỡ phép chia
nhỏ S. Tam giác của tập P (n>=2 ñiểm) là Delaunay nếu và chỉ nếu
ñường tròn qua nó không chứa ñiểm thứ tư.
2.4 Thuật toán Delaunay
Thuật toán tạo lưới tam giác Delaunay là một bài toán cơ bản
trong hình học tính toán và nó ñược sử dụng trong rất nhiều lĩnh vực
như hệ thống thông tin ñịa GIS, phần tử hữu hạn, ñồ họa máy tính và
ña phương tiện…
Để xây dựng lưới tam giác Delaunay từ tập hợp ñiểm ñầu
vào ta có thể chia thành các hướng tiếp cận sau:
a) Hướng tiếp cận chia ñể trị
Đầu tiên, tập ñiểm ñầu vào ñược chia thành các tập con, thực
hiện xây dựng lưới tam giác cho mỗi tập con rồi hợp nhất lại ñể tạo
ra lưới tam giác kết quả cuối cùng. Tuy nhiên, phần hợp nhất các kết
quả con thường cài ñặt khá phức tạp. Giải pháp này ñược ñề cập bởi
Dwyer trong công trình [6].
b) Hướng tiếp cận sử dụng dòng quét
9
Giải thuật theo hướng tiếp cận này ñã ñược ñưa ra bởi
Fortune [7], sau ñó ñược tổng hợp lại bởi de Berg trong công trình
[5]. Fortune ñã phát triển giải thuật xây dựng ñồ thị ñối ngẫu giữa
lưới tam giác Delaunay và sơ ñồ Voronoi. Việc cài ñặt giải thuật là
khá phức tạp.
c) Hướng tiếp cận thêm từng ñiểm tuần tự
Các giải thuật thuộc hướng tiếp cận này khá ñơn giản ñể cài
ñặt. Giả sử chúng ta có lưới tam giác Delaunay ñược xây dựng từ i-1
ñiểm. Điểm thứ i sẽ ñược thêm vào lưới tam giác theo cách sau: Xác
ñịnh tam giác chứa ñiểm i mới thêm vào lưới. Phân rã tam giác ñó
thành các tam giác con thuộc lưới và hiệu chỉnh thoả ñiều kiện
Delaunay [4].
2.5 Phương pháp chia nhỏ bề mặt lưới tam giác Loop
Các mô hình 3D ñược tạo ra từ các tập hợp ñiểm bằng giải
thuật Delaunay sẽ tạo ra các bề mặt lưới tam giác thô. Để tạo ra ñược
các bề mặt lưới mịn hơn ta có thể áp dụng các thuật toán chia nhỏ bề
mặt lưới.
Phương pháp Loop chia nhỏ bề mặt lưới là dựa vào các lưới
tam giác ñầu vào. Với bề mặt lưới ñầu vào là các bề mặt tam giác
ñược tạo ra từ phương pháp tạo lưới thông qua giải thuật Delaunay.
Trong phạm vi của luận văn này, tôi ñã tập trung vào phương pháp
Loop chia nhỏ bề mặt lưới, bằng các phép tính xấp xỉ, nhằm tạo ra
các bề mặt có tính liên tục. Với thuật toán Loop, chia nhỏ mỗi mặt
trong lưới ñầu vào ñược chia thành bốn mặt nhỏ hơn.
10
Hình 2.16 Biểu diễn giải thuật chia nhỏ Loop
Mô hình chia nhỏ theo phương pháp Loop tiến hành chia nhỏ
mặt lưới tam giác bằng cách thực hiện một số bước lặp. Chú ý rằng
các ña giác tạo nên các bề mặt phải là các tam giác, các bề mặt không
thể là những ña giác phẳng bất kỳ.
Giải thuật này do Charles Teorell Loop ñề cập trong [12],
ông ñã cải tiến giải thuật chia nhỏ mỗi tam giác thành 4 tam giác con.
Giải thuật này cũng ñược biết ñến với tên là giải thuật chia nhỏ Loop
nhị phân.
Giải thuật Loop nhị phân bắt ñầu bằng tập ñiểm là các ñỉnh
của tam giác. Mỗi phép lặp tính một tập các cạnh và các ñiểm ñỉnh
mới tạo nên các ñỉnh mới của các tam giác nhỏ hơn. Đặc biệt, ñối với
mỗi cạnh và một ñiểm ñỉnh mới thì một ñiểm cạnh mới ñược tính cho
mỗi ñỉnh của lưới tam giác.
Giải thuật chia nhỏ Loop ñược chia làm hai bước. Bước ñầu
tiên tạo ra tất cả các ñiểm và tam giác mới, và bước thứ hai sẽ ñịnh vị
lại tất cả các ñiểm cũ. Giải thuật Loop là giải thuật tính xấp xỉ nghĩa
là các ñỉnh sẽ ñược hiệu chỉnh lại trong suốt quá trình phân chia.
Các ñỉnh lẻ là các ñỉnh ñược thêm vào trong suốt quá trình
phân chia trong khi ñó các ñỉnh chẵn là các ñỉnh sẵn có trước lúc
chia. Các cạnh biên là cạnh nằm trên ñường biên của lưới. Nghĩa là,
nếu tồn tại một cạnh ab của tam giác mà không có chung với cạnh
tam giác nào khác thì nó chính là cạnh biên. Đỉnh a, b có thể mô tả
11
như là các ñỉnh biên. Các cạnh bên trong (không phải cạnh biên) là
tập bổ sung vào bất cứ cạnh nào có chung 2 tam giác. Một ñỉnh bên
trong chỉ nằm trên các cạnh bên trong.
Hình 2.18 Hình minh họa ñỉnh lẻ và ñỉnh chẵn
Chương 3 PHÂN TÍCH XÂY DỰNG CHƯƠNG TRÌNH XÂY
DỰNG BỀ MẶT LƯỚI 3D
Việc tái tạo lại mô hình từ các vật thể từ các ñối tượng thực
bằng công nghệ tái tạo mô hình vật thể trên máy tính. Việc thu thập
dữ liệu của ñối tượng thực dưới dạng các ñiểm, liên kết các dữ liệu
và tái tạo lại mô hình mô hình của ñối tượng thực trong không gian
3D. Từ các dữ liệu ñiểm, một lưới tam giác ñược xây dựng ñể liên
kết các ñiểm 3 chiều trong không gian sử dụng thuật toán Delaunay.
Mô hình ñối tượng ñược số hoá, sau khi thực hiện một số bước tinh
chỉnh, làm mịn, vá lỗ thủng hoặc chia nhỏ lưới tam giác ñể tăng
cường chi tiết hoá mô hình số bằng giải thuật chia nhỏ Loop.
1/8
1/8
3/8
3/8
a
1/2
1/2
1/8
1/8 3/4
1-kβ
β
β
β
β
β
β
(a) ñỉnh lẻ (b) ñỉnh chẳn
a
a
b
a
c
a
d
a
v
a
12
Các bước xây dựng chương trình tái tạo bề mặt lưới từ tập
hợp ñiểm 3D và phương pháp chia nhỏ bề mặt lưới ñược minh họa
như sau:
Hình 3.1 Sơ ñồ tạo lưới tam giác Delaunay và làm mịn
3.1 Tổ chức dữ liệu bề mặt lưới
Ngày nay, kỹ thuật mô hình hoá các ñối tượng 3D ñã có
nhiều ứng dụng rộng rãi, ñặc biệt trong thiết kế và biểu diễn các ñối
tượng ba chiều. Việc tái lập lại các ñối tượng 3D thực bằng các sử
dụng cơ chế tái tạo ngược bằng các thu thập dữ liệu các ñối tượng
thực dưới dạng ñiểm ñể liên kết các dữ liệu và tái tạo lại mô hình. Để
lưu trữ tập hợp ñiểm 3D thu ñược và mô hình hóa hình học ta sử
dụng ngôn ngữ VRML (Virtual Reality Modeling Language).
3.2 Xây dựng lưới tam giác Delaunay từ tập hợp ñiểm rời rạc
3D
3.2.1 Sơ ñồ khối của thuật toán ñược mô tả như sau:
Không có nhận xét nào:
Đăng nhận xét