Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00047
NÂNG CAO CHẤT LƯỢNG TÁI TẠO MẶT CONG B-SPLINE TAM GIÁC
DỰA TRÊN HIỆU CHỈNH VECTƠ NÚT
Lê Thị Thu Nga1, Nguyễn Tấn Khôi2, Nguyễn Thanh Thủy3
1
Khoa Công nghệ Thông tin, Đại học Quy Nhơn, Việt Nam
2
Khoa Công nghệ Thông tin, Đại học Bách khoa, Đại học Đà Nẵng, Việt Nam
3
Đại học Công nghệ, Đại học Quốc gia Hà Nội, Việt Nam
lenga248@gmail.com, ntkhoi@dut.udn.vn, nguyenthanhthuy@vnu.edu.vn
TÓM TẮT: Tái tạo mặt cong từ mô hình lưới mô phỏng bề mặt của đối đượng 3D vẫn đang là vấn đề quan tâm và có nhiều ứng
dụng thực tiễn. Mặt cong tham số B-spline tam giác tái tạo được cho phép biểu diễn các bề mặt có hình dáng đa dạng, thuận tiện
khi hiệu chỉnh bề mặt thông qua các đỉnh điều khiển. Bên cạnh các đỉnh điều khiển, vị trí các vectơ nút trên miền tham số cũng ảnh
hưởng đến hình dáng của mặt cong B-spline tam giác. Bài viết này để xuất kỹ thuật nhằm xác định các vectơ nút của B-spline tam
giác bậc 2, 3, 4 dựa trên tỉ lệ độ lớn giữa các góc, cạnh của các tam giác trên miền tham số, áp dụng cho cả các nút bên trong và
nút ở biên. Việc xác định các nút được kiểm tra thỏa điều kiện sinh nút, tránh trường hợp cộng tuyến giữa các nút được tạo ra. Kết
quả được áp dụng trong quá trình tái tạo B-spline tam giác từ lưới tam giác 3D ban đầu bằng phương pháp dịch chuyển hình học.
Thực nghiệm cho thấy chất lượng của mặt cong B-splỉne tam giác tái tạo được cải thiện rõ rệt.
Từ khóa: Tái tạo mặt cong, chất lượng tái tạo, B-spline tam giác, vectơ nút, hiệu chỉnh nút.
I. GIỚI THIỆU
Mô hình hình học trong không gian ba chiều đóng vai trò quan trọng trong quá trình mô phỏng, thiết kế và tái
tạo bề mặt các đối tƣợng vật lý trên máy tính. Bên cạnh mô hình lƣới đa giác, mặt cong tham số cũng đang đƣợc sử
dụng rộng rãi để mô tả bề mặt 3D của đối tƣợng thực. Mặt cong tham số không chỉ cho phép biểu diễn bề mặt trơn
mềm, liên tục, điều chỉnh bề mặt cục bộ thông qua các đỉnh điều khiển; mà còn có thể tƣơng tác chính xác đến từng
điểm trên bề mặt của đối tƣợng [5, 8]. Nhờ đó, bên cạnh việc biểu diễn bề mặt của đối tƣợng trên máy tính trông thực
hơn, mặt cong tham số còn đóng vai trò đắc lực cho các ứng dụng đòi hỏi khả năng tƣơng tác với bề mặt của đối tƣợng
nhƣ: mô hình hóa hình dạng đối tƣợng ảo, phát hiện va chạm, biến dạng bề mặt, tính toán phản lực trong công nghệ
thực tế ảo; khôi phục lại bề mặt trong tái tạo ngƣợc; ánh xạ mẫu nền, kỹ xảo hoạt hình trong đồ họa máy tính; mô
phỏng bề mặt địa hình, xác định độ cao, nếp đứt gãy trong hệ thống thông tin địa lý; xác định khối lƣợng, diện tích bề
mặt trong tính toán các đặc tính vật lý; tính toán sức căng, độ truyền nhiệt trong phƣơng pháp phần tử hữu hạn,… Các
mặt cong Bézier, B-spline, NURBS,… trên miền tham số tứ giác từ lâu đã trở thành công cụ chính và là chuẩn công
nghiệp trong các hệ thống CAD/CAM [5].
Trong các ứng dụng mô hình hóa, để đáp ứng nhu cầu sử dụng của ngƣời dùng, ngƣời ta cần khai thác thế mạnh
của cả hai mô hình lƣới đa giác và mặt cong tham số. Do đó, nhu cầu chuyển đổi qua lại giữa hai mô hình này cho phép
khai thác hiệu quả các ƣu điểm của chúng, nhằm hỗ trợ trong thao tác hiển thị cũng nhƣ phân tích, tƣơng tác với bề mặt
đối tƣợng. Tái tạo mặt cong từ mô hình lƣới mô phỏng bề mặt của đối đƣợng 3D vẫn đang là vấn đề quan tâm và có
nhiều ứng dụng thực tiễn. Các nghiên cứu chủ yếu tái tạo mặt cong phân mảnh hoặc mặt cong trên miền tham số tứ
giác nhƣ Bézier, B-spline,…[1, 2, 9, 12]. Tuy nhiên, với các mặt cong trên miền tham số tứ giác, để biểu diễn bề mặt
có hình dạng bất kỳ, các mặt cong này cần phải kết nối với nhau. Kết quả thƣờng xuất hiện các kẽ hở, nếp gấp, đặc biệt
tại các đỉnh đặc biệt (có nhiều hơn 4 tứ giác liền kề) [4, 9].
Tái tạo mặt cong trên miền tham số tam giác, đặc biệt là B-spline trên miền tham số tam giác, còn gọi là B-
spline tam giác, đang đƣợc quan tâm trong những năm gần đây [7, 10 ]. Ƣu điểm của mặt cong này là sự kết nối liên
tục và tự động giữa các mảnh B-spline liền kề, cho phép biểu diễn bề mặt trơn mềm toàn cục với hình dáng đa dạng và
hiệu chỉnh bề mặt thông qua các đỉnh điều khiển. Bên cạnh các đỉnh điều khiển, vị trí các vectơ nút trên miền tham số
cũng ảnh hƣởng đến hình dáng của mặt cong B-spline tam giác [6, 11]. Tƣơng tự B-spline tứ giác, B-spline tam giác
cho phép biểu diễn mặt cong trên miền xác định là lƣới phẳng tam giác. Tuy nhiên, không giống B-spline tứ giác, B-
spline tam giác không tƣơng quan với mặt cong Bézier tam giác [3]. Do đó, việc xác định các vectơ nút vẫn đang là
mối quan tâm và cần phải giải quyết các trƣờng hợp cộng tuyến giữa các nút.
Bài viết này để xuất kỹ thuật nhằm xác định các vectơ nút của B-spline tam giác bậc 2, 3, 4 dựa trên tỉ lệ độ lớn
giữa các góc, cạnh của các tam giác trên miền tham số, áp dụng cho cả các nút bên trong và nút ở biên. Việc xác định
các nút đƣợc kiểm tra thỏa điều kiện sinh nút, tránh trƣờng hợp cộng tuyến giữa các nút đƣợc tạo ra. Kết quả đƣợc áp
dụng trong quá trình tái tạo B-spline tam giác từ lƣới tam giác 3D ban đầu bằng phƣơng pháp dịch chuyển hình học.
Thực nghiệm cho thấy chất lƣợng của mặt cong B-splỉne tam giác tái tạo đƣợc cải thiện rõ rệt.
Phần còn lại của bài viết gồm các nội dung sau: Phần 2 trình bày về biểu diễn toán học, vectơ nút và ảnh hƣởng
của vectơ nút đối với hình dạng mặt cong B-spline tam giác; Phần 3 đề xuất phƣơng pháp xác định vectơ nút trên miền
- 354 NÂNG CAO CHẤT LƢỢNG TÁI TẠO MẶT CONG B-SPLINE TAM GIÁC DỰA TRÊN HIỆU CHỈNH VECTƠ NÚT
tham số tam giác của mặt cong; Phần 4 trình bày các kết quả thực nghiệm; và cuối cùng tóm tắt một số kết quả đạt
đƣợc.
II. MẶT CONG B-SPLINE TAM GIÁC
2.1. Biểu diễn B-spline tam giác
Mặt cong B-spline tam giác bậc n là sự kết hợp tuyến tính của các Spline đơn hình, tự động kết nối liên tục cấp
n-1 mà không cần thực hiện kết nối giữa các mảnh cong [3].
Gọi T 2
là lƣới tam giác phẳng có hình dạng bất kỳ. Với mỗi đỉnh vi T , thêm vào n+1 nút {vi ,0 ,..., vi ,n }, với
vi ,0 vi , để tạo thành vectơ nút của đỉnh này. Đặt i j k n . Với mỗi tam giác I (v0 , v1 , v2 ) T , chọn
(n 1)(n 2) tập con V I {v0,0 ,...v0,i , v1,0 ,...v1, j , v2,0 ,...v2,k } gồm n+3 nút từ 3 vectơ nút liên kết với tam giác I. Mỗi tập
2
con V I trở thành miền tham số của một Spline đơn hình M (u | V I ) bậc n. Kết hợp tuyến tính của các Spline đơn hình này
chính là mặt cong B-spline tam giác bậc n, đạt liên tục C n 1
trên miền tham số tam giác T 2
.
Ảnh của tham số u I , với I T , chính là điểm trên mặt cong B-spline tam giác bậc n, đƣợc xác định bởi
công thức [6]:
F (u) N I (u)p I (1)
I T n
Trong đó:
Các điểm p I 3
là các đỉnh điều khiển B-spline, tạo thành lƣới điều khiển của mặt cong;
Hàm N I (u) là hàm cơ sở B-spline. Đây chính là Spline đơn hình xác định trên tập nút V I và đƣợc
I
chuẩn hóa có tổng bằng 1, với V {v0,i , v1, j , v2, k } :
N I (u) det(V I ) M (u | V I ) (2)
(a) (b)
Hình 1. Mặt cong B-spline bậc hai (a) và miền tham số tƣơng ứng (b).
Mặt cong B-spline tam giác có các tính chất hình học nhƣ [6,11]: Bất biến đối với phép biến đổi affine, tính bao
lồi, điều khiển cục bộ, tính liên tục, biểu diễn bề mặt có hình dạng bất kỳ.
2.2. Ảnh hưởng của vectơ nút đối với hình dạng mặt cong B-spline tam giác
Với mặt cong B-spline tam giác, bên cạnh các đỉnh điều khiển, vectơ nút cũng tham gia trong việc xác định mặt
cong. Do đó, hình dáng của mặt cong không chỉ phụ thuộc vào vị trí của các đỉnh điều khiển mà còn chịu ảnh hƣởng
bởi vị trí của các nút trên miền tham số [3, 7].
Mặc dù B-spline tam giác tự động liên tục giữa các mảnh cong liền kề, tuy nhiên trong trƣờng hợp đa nút hoặc
các nút trong vectơ nút nằm trên các cạnh của tam giác trên miền tham số, thì hình dáng mặt cong thể hiện rõ nét sự
góc cạnh, đứt gãy, giảm độ liên tục. Ví dụ, thông thƣờng để đảm bảo tính liên tục, các nút của một B-spline bậc 2 có
dạng nhƣ trong Trƣờng hợp 1 (Hình 2.a). Tuy nhiên, nếu đặt các nút trên một cạnh của tam giác thuộc miền tham số thì
B-spline bậc 2 thu đƣợc sẽ giảm độ liên tục nhƣ minh họa ở Trƣờng hợp 4 của Hình 3.a.
Trƣờng hợp bình thƣờng và đặc biệt của các vectơ nút trên miền tham số, cùng với B-spline kết quả tƣơng ứng,
đƣợc minh họa trong Hình 2 và 3 [6].
- Lê Thị Thu Nga, Nguyễn Tấn Khôi, Nguyễn Thanh Thủy 355
(a) Trƣờng hợp 1 (b) Trƣờng hợp 2 (c) Trƣờng hợp 3
Hình 2. Các trƣờng hợp bình thƣờng của vectơ nút và mặt cong B-spline tƣơng ứng.
(a) Trƣờng hợp 4 (b) Trƣờng hợp 5 (c) Trƣờng hợp 6
Hình 3. Các trƣờng hợp đặc biệt của vectơ nút và mặt cong B-spline tƣơng ứng.
III. XÁC ĐỊNH VECTƠ NÚT TRÊN MIỀN THAM SỐ TAM GIÁC
Miền tham số của mặt cong B-spline là một lƣới tam giác phẳng, mỗi đỉnh đƣợc gắn với một vectơ nút. Các tam
giác có chung đỉnh sẽ có chung vectơ nút. Dựa trên ý tƣởng các nút của vectơ nút phải cân đối, tỉ lệ với góc và cạnh
liên kết với đỉnh gắn với vectơ nút; phần này đề xuất cách xác định vị trí các nút trong vectơ nút trên miền tham số của
các B-spline tam giác bậc 2, 3 và 4. Từ đó hỗ trợ cho việc dựng mặt cong B-spline và điều chỉnh các vectơ nút trong
quá trình tái tạo mặt cong này.
Mỗi đỉnh vi trong miền tham số tam giác liên kết với một vectơ nút V. Số nút trong vectơ nút V phụ thuộc vào
bậc của mặt cong. Ví dụ, với mặt cong bậc hai thì số nút của vectơ nút là 2, mặt cong bậc ba thì số nút của vectơ nút là
3,… Trong đó, nút đầu tiên chính là đỉnh vi hay vi0, các nút tiếp theo đƣợc ký hiệu là vi1, vi2,…, vij, với j = 0..(n-1) và n
là bậc của mặt cong.
Hình 4. Điều kiện sinh nút: (a), (b), (c) tƣơng ứng với các điều kiện (1), (2), (3).
- 356 NÂNG CAO CHẤT LƢỢNG TÁI TẠO MẶT CONG B-SPLINE TAM GIÁC DỰA TRÊN HIỆU CHỈNH VECTƠ NÚT
Dựa trên các trƣờng hợp đặc biệt của vectơ nút đƣợc nêu ở mục II.B, các nút vij trong vectơ nút V ứng với đỉnh
vi cần thỏa các điều kiện sinh nút nhƣ sau (Hình 4):
(1). Các nút vij không nằm trên đƣờng thẳng chứa các cạnh chung đỉnh vi;
(2). Các nút vij không nằm trên cùng một đƣờng thẳng đi qua đỉnh vi;
(3). Các nút vij không nằm trong tam giác không chung đỉnh với đỉnh vi.
Để đảm bảo liên tục, tránh xuất hiện các thành phần đứt gãy trên mặt cong, các tam giác thành phần tạo nên
miền tham số của các Spline đơn hình có dạng gần với tam giác cân càng tốt. Do đó, các nút đƣợc xác định tại một
đỉnh sẽ ƣu tiên đặt tại góc lớn nhất trong số các góc cùng chung đỉnh này. Điều này cũng làm thỏa điều kiện (1), hạn
chế các nút nằm trên cùng đƣờng thẳng nhƣ nêu ở điều kiện (2). Mặt khác, để thỏa điều kiện (3), khoảng cách giữa các
nút cần tỉ lệ với cạnh ngắn nhất và số bậc của mặt cong (vì mặt bậc cong hai cần xác định hai nút cho vectơ nút, mặt
cong bậc ba cần xác định ba nút cho vectơ nút,…).
Ứng với vị trí của một đỉnh nằm bên trong hay trên biên của lƣới tam giác phẳng miền tham số, ta cần phải xác
định vị trí nút của vectơ nút bên trong (vectơ nút trong) và vectơ nút ở biên (vectơ nút biên).
3.1. Xác định vectơ nút của mặt cong B-spline bậc hai
Với mặt cong B-spline tam giác bậc hai, vectơ nút V {vi 0 , vi1} tại mỗi đỉnh gồm hai nút. Trong đó, nút vi0
chính là đỉnh vi, ta cần xác định vị trí nút vi1.
Hình 5. Xác định vectơ nút của mặt cong bậc hai: vectơ nút trong (a) và vectơ nút biên (b,c).
Xác định vectơ nút trong
Vectơ nút trong trên miền tham số của mặt cong bậc n = 2 xác định nhƣ sau (Hình 5.a):
Xác định tất cả các tam giác chung đỉnh vi;
Xác định đƣờng thẳng d đi qua vi, là phân giác của góc lớn nhất α trong số các góc có chung đỉnh vi;
Xác định khoảng cách D bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn nhất α;
Nút vi1 đặt bên trong tam giác có góc lớn nhất α, trên đƣờng thẳng d và cách vi với khoảng cách D;
Kiểm tra các điều kiện sinh nút. Nếu không thỏa các điều kiện này, cần thay đổi vị trí đƣờng thẳng d để
thỏa điều kiện (1) hoặc (2), giảm khoảng cách D để thỏa điều kiện (3).
Xác định vectơ nút biên
Vectơ nút biên trên miền tham số của mặt cong bậc n = 2 xác định nhƣ sau:
Xác định tất cả các tam giác chung đỉnh vi .
- Nếu chỉ có một tam giác (Hình 5.b):
+ Xác định góc trong α chứa đỉnh vi;
+ Xác định đƣờng thẳng d đi qua vi, là phân giác của góc trong α;
+ Xác định khoảng cách D bằng 1/n độ dài cạnh ngắn nhất trong số hai cạnh có chung đỉnh vi;
+ Nút vi1 đặt bên ngoài tam giác có góc trong α, trên đƣờng thẳng d và cách vi với khoảng cách D.
- Nếu có nhiều tam giác (Hình 5.c):
+ Xác định góc ngoài β chứa đỉnh vi;
+ Xác định đƣờng thẳng d đi qua vi , là phân giác của góc ngoài β;
- Lê Thị Thu Nga, Nguyễn Tấn Khôi, Nguyễn Thanh Thủy 357
+ Xác định khoảng cách D bằng 1/n độ dài cạnh ngắn nhất trong số các cạnh có chung đỉnh vi ;
+ Nút vi1 đặt ở góc ngoài β, trên đƣờng thẳng d và cách vi với khoảng cách D.
Kiểm tra các điều kiện sinh nút. Nếu không thỏa các điều kiện này, cần thay đổi vị trí đƣờng thẳng d để
thỏa điều kiện (1) hoặc (2), giảm khoảng cách D để thỏa điều kiện (3).
3.2. Xác định vectơ nút của mặt cong B-spline bậc ba
Với mặt cong B-spline tam giác bậc ba, vectơ nút V {vi 0 , vi1 , vi 2 } tại mỗi đỉnh gồm ba nút. Trong đó, nút vi0
chính là đỉnh vi, ta cần xác định vị trí hai nút vi1 và vi2 còn lại.
Xác định vectơ nút trong
Vectơ nút trong trên miền tham số của mặt cong bậc n = 3 đƣợc xác định theo các bƣớc nhƣ sau (Hình 6.a):
Xác định tất cả các tam giác chung đỉnh vi;
Xác định các đƣờng thẳng d1, d2 đi qua vi, là phân giác của các góc lớn nhất α1, lớn thứ hai α2 trong số
các góc có chung đỉnh vi;
Xác định các khoảng cách D1 và D2. Trong đó D1 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa
góc lớn nhất α1 và D2 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn thứ hai α2;
Nút vi1 đặt bên trong tam giác có góc lớn nhất α1, trên đƣờng thẳng d1 và cách vi với khoảng cách D1. Nút
vi2 đƣợc đặt bên trong tam giác có góc lớn thứ hai α2, trên đƣờng thẳng d2 và cách vi với khoảng cách D2;
Kiểm tra các điều kiện sinh nút. Nếu không thỏa các điều kiện này, cần thay đổi vị trí các đƣờng thẳng d1
và d2 để thỏa điều kiện (1) hoặc (2), giảm khoảng cách D1 và D2 để thỏa điều kiện (3).
Hình 6. Xác định vectơ nút của mặt cong bậc ba: vectơ nút trong (a) và vectơ nút biên (b,c,d).
Xác định vectơ nút biên
Vectơ nút biên trên miền tham số của mặt cong bậc n = 3 xác định nhƣ sau:
Xác định tất cả các tam giác chung đỉnh vi;
- Nếu chỉ có một tam giác (Hình 6.b)
+ Xác định góc trong α chứa đỉnh vi;
+ Xác định các đƣờng thẳng d1, d2 đi qua vi và chia góc trong α thành ba phần đều nhau, tƣơng ứng
là 1 / n và 2 2 / n ;
+ Xác định các khoảng cách D1 và D2, trong đó D1 bằng 1/n độ dài cạnh gần d1 hơn và D2 bằng 1/n
độ dài cạnh gần d2 hơn;
- 358 NÂNG CAO CHẤT LƢỢNG TÁI TẠO MẶT CONG B-SPLINE TAM GIÁC DỰA TRÊN HIỆU CHỈNH VECTƠ NÚT
+ Các nút vi1 và vi2 đƣợc đặt bên ngoài tam giác có góc trong α, lần lƣợt trên đƣờng thẳng d1 và d2,
cách vi với các khoảng cách D1 và D2 tƣơng ứng.
- Nếu có nhiều tam giác
+ Xác định góc ngoài β chứa đỉnh vi;
+ Nếu β 180 (Hình 6.d)
o Xác định các đƣờng thẳng d1, d2 đi qua vi, là phân giác của các góc lớn nhất α1 và lớn thứ hai
α2 trong số các góc có chung đỉnh vi;
o Xác định các khoảng cách D1 và D2, trong đó D1 bằng 1/n độ dài cạnh ngắn nhất thuộc tam
giác chứa góc lớn nhất α1 và D2 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn
thứ hai α2.
+ Các nút vi1 và vi2 đặt bên trong góc β (ngoài các tam giác chung đỉnh vi), lần lƣợt trên đƣờng thẳng
d1 và d2, cách vi với khoảng cách D1 và D2 tƣơng ứng.
Kiểm tra các điều kiện sinh nút. Nếu không thỏa các điều kiện này, thay đổi vị trí các đƣờng thẳng d1 và
d2 để thỏa điều kiện (1) hoặc (2), giảm khoảng cách D1 và D2 để thỏa điều kiện (3).
3.3. Xác định vectơ nút của mặt cong B-spline bậc bốn
Với mặt cong B-spline tam giác bậc bốn, vectơ nút V {vi 0 , vi1 , vi 2 , vi 3} tại mỗi đỉnh gồm bốn nút. Trong đó, nút
vi0 chính là đỉnh vi, ta cần xác định vị trí các nút vi1, vi2 và vi3.
Xác định vectơ nút trong
Tƣơng tự mặt cong bậc ba, vectơ nút trong trên miền tham số của mặt cong bậc n = 4 đƣợc xác định nhƣ sau:
Xác định tất cả các tam giác chung đỉnh vi;
Xác định các đƣờng thẳng d1, d2, d3 đi qua vi, là phân giác của các góc lớn nhất α1, lớn thứ hai α2 và lớn
thứ ba α3 trong số các góc có chung đỉnh vi;
Xác định các khoảng cách D1, D2 và D3, trong đó D1 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa
góc lớn nhất α1, D2 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn thứ hai α2 và D3 bằng 1/n
độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn thứ ba α3;
Nút vi1 đặt bên trong tam giác có góc lớn nhất α1, trên đƣờng thẳng d1 và cách vi với khoảng cách D1. Nút
vi2 đặt bên trong tam giác có góc lớn thứ hai α2, trên đƣờng thẳng d2 và cách vi với khoảng cách D2. Nút
vi3 đặt bên trong tam giác có góc lớn thứ ba α3, trên đƣờng thẳng d3 và cách vi với khoảng cách D3;
Kiểm tra các điều kiện sinh nút. Nếu không thỏa các điều kiện này, thay đổi vị trí các đƣờng thẳng d1, d2,
d3 để thỏa điều kiện (1) hoặc (2), giảm khoảng cách D1, D2, D3 để thỏa điều kiện (3).
Xác định vectơ nút biên
Vectơ nút biên trên miền tham số của mặt cong bậc n = 4 xác định nhƣ sau:
Xác định tất cả các tam giác chung đỉnh vi;
Nếu chỉ có một hoặc hai tam giác
- Xác định góc trong α đƣợc tạo bởi hai cạnh biên có đỉnh chung vi;
- Xác định các đƣờng thẳng d1, d2, d3 đi qua vi và chia góc trong α thành bốn phần đều nhau, tƣơng ứng
là 1 / n , 2 2 / n và 3 3 / n ;
- Xác định các khoảng D1, D2 và D3, trong đó D1 bằng 1/n độ dài cạnh gần d1 hơn, D3 bằng 1/n độ dài
cạnh gần d3 hơn và D2 = (D1 + D3)/2;
- Lê Thị Thu Nga, Nguyễn Tấn Khôi, Nguyễn Thanh Thủy 359
- Các nút vi1, vi2 và vi3 đƣợc đặt bên ngoài góc α, lần lƣợt trên đƣờng thẳng d1, d2 và d3 , cách vi với các
khoảng cách D1, D2 và D3 tƣơng ứng.
Nếu có nhiều tam giác
- Xác định góc ngoài β chứa đỉnh vi ;
- Nếu β 180
+ Xác định các đƣờng thẳng d1, d2, d3 đi qua vi và là phân giác của các góc lớn nhất α1, lớn thứ hai
α2 và lớn thứ ba α3 trong số các góc có đỉnh chung vi ;
+ Xác định các khoảng cách D1, D2 và D3, trong đó D1 bằng 1/n độ dài cạnh ngắn nhất thuộc tam
giác chứa góc lớn nhất α1, D2 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn thứ hai
α2 và D3 bằng 1/n độ dài cạnh ngắn nhất thuộc tam giác chứa góc lớn thứ ba α3.
- Các nút vi1, vi2 và vi3 đƣợc đặt bên trong góc β (ngoài các tam giác chung đỉnh vi), lần lƣợt trên các
đƣờng thẳng d1, d2 và d3 và cách vi với các khoảng cách D1, D2 và D3 tƣơng ứng.
Kiểm tra các điều kiện sinh nút. Nếu không thỏa các điều kiện này, thay đổi vị trí các đƣờng thẳng d1, d2
và d3 để thỏa điều kiện (1) hoặc (2), giảm các khoảng cách D1, D2 và D3 để thỏa điều kiện (3).
IV. KẾT QUẢ THỰC NGHIỆM
Trong quá trình tái tạo mặt cong B-spline tam giác bằng phƣơng pháp dịch chuyển hình học, để xấp xỉ mặt cong
với lƣới tam giác 3D ban đầu, bên cạnh việc điều chỉnh vị trí các đỉnh điều khiển, vị trí các nút trong vectơ nút trên
miền tham số cũng đƣợc xác định và cập nhật lại. Để thấy đƣợc hiệu quả của việc cập nhật vị trí các nút của vectơ nút
trong quá trình tái tạo B-spline tam giác, trong phần này chúng tôi tiến hành thử nghiệm trên các bộ dữ liệu mẫu Hat,
Mountain và Wings [7], tƣơng ứng với ba dạng mặt cong B-spline tam giác bậc 2, 3, 4. Kết quả đạt đƣợc sau k = 9
bƣớc dịch chuyển hình học.
Gọi avg là độ lệch trung bình tính đƣợc sau bƣớc dịch chuyển thứ k và N là tỉ lệ hội tụ của mặt cong so với lƣới
tam giác ban đầu sau k bƣớc dịch chuyển. Giá trị N đƣợc xác định bằng tỉ lệ phần trăm của số diểm dữ liệu mà mặt
cong đi qua so với tổng số điểm dữ liệu của lƣới tam giác ban đầu. Thông tin dữ liệu ban đầu và các mặt cong B-spline
tam giác đạt đƣợc thể hiện trong Bảng 1. Các kết quả này đƣợc thực hiện trên Intel Core i5 CPU 2.67GHz với 4GB
RAM.
Bảng 1. Các mô hình thực nghiệm và mặt cong tham số kết quả đạt đƣợc tƣơng ứng.
Lƣới ban đầu Thời gian B-spline kết quả
Bộ dữ liệu [7]
Số điểm Số mặt (s) avg N bậc
Hat 3681 7168 128 0.004034 91.979% 2
Mountain 854 1600 94 0.005159 89.337% 3
Wings 833 1536 107 0.004674 91.475% 4
Hình 7 minh họa kết quả tái tạo mặt cong B-splỉne từ lƣới tam giác ban đầu sau k = 9 bƣớc dịch chuyển hình
học. Thông tin chi tiết các mô hình lƣới và mặt cong B-spline kết quả đƣợc liệt kê trong Bảng 1. Các mô hình lƣới thử
nghiệm trên bộ dữ liệu Hat (Hình 7.a), Mauntain (Hình 7.b) và Wings (Hình 7.c). Trong đó: hàng 1 mô tả lƣới dữ liệu
ban đầu, hàng 2 biểu diễn mặt cong đạt đƣợc khi dịch chuyển các đỉnh điều khiển, hàng 3 hiển thị mặt cong đạt đƣợc
khi dịch chuyển các đỉnh điều khiển và cập nhật vectơ nút, và hàng cuối cùng là miền tham số của mặt cong ở hàng 3.
So với mô hình Hat và Wings, mô hình Mauntain cho kết quả có phần thấp hơn ( avg = 0.005159, N =89.337%). Điều này
có thể lý giải là do các tam giác trên miền tham số của mặt cong này (góc dƣới trái trên miền tham số trong Hình 7.b)
có chất lƣợng chƣa tốt, do đó mặt cong dựng đƣợc từ mô hình này xuất hiện các thành phần góc, nhọn. Sự phủ lấp của
lƣới ban đầu so với mặt cong đạt đƣợc ở hàng 3 cho thấy việc cập nhật vectơ nút mang lại hiệu quả trong quá trình tái
tạo mặt cong.
Hình 8 cho thấy sự cải thiện rõ rệt về chất lƣợng của mặt cong B-spline tái tạo đƣợc thông qua độ lệch trung
bình avg (Hình 8.a) và tỉ lệ hội tụ N (Hình 8.b). Bằng cách áp dụng đồng thời việc hiệu chỉnh vị trí của các đỉnh điều
khiển và cập nhật vị trí các nút trong vectơ nút trên miền tham số của mặt cong trong quá trình tái tạo, kết quả cho thấy
độ lệch trung bình avg giảm và tỉ lệ hội tụ N tăng so với chỉ áp dụng việc cập nhật các đỉnh điều khiển.
- 360 NÂNG CAO CHẤT LƢỢNG TÁI TẠO MẶT CONG B-SPLINE TAM GIÁC DỰA TRÊN HIỆU CHỈNH VECTƠ NÚT
(a) (b) (c)
Hình 7. Các mặt cong B-spline tam giác tái tạo: lƣới ban đầu (hàng 1),
mặt cong đạt đƣợc khi dịch chuyển các đỉnh điều khiển (hàng 2),
mặt cong đạt đƣợc khi dịch chuyển các đỉnh điều khiển và cập nhật vectơ nút (hàng 3),
và miền tham số của mặt cong ở hàng 3 (hàng 4) ứng với các bộ dữ liệu Hat (a), Mauntain (b) và Wings (c).
(a) (b)
Hình 8. So sánh chất lƣợng của các mặt cong B-spline đạt đƣợc theo:
độ lệch trung bình avg (a) và tỉ lệ hội tụ N (b).
- Lê Thị Thu Nga, Nguyễn Tấn Khôi, Nguyễn Thanh Thủy 361
V. KẾT LUẬN
Mặt cong tham số B-spline tam giác có ƣu điểm vƣợt trội, liên tục tự động giữa các mảnh liền kề mà không cần
kết nối. B-spline tam giác cho phép biểu diễn bề mặt trơn mềm toàn cục với hình dáng đa dạng, hứa hẹn trong nhiều
ứng dụng thực tiễn. Bên cạnh các đỉnh điều khiển thì vectơ nút trên miền tham số cũng đóng vai trò quan trọng trong
việc điều chỉnh hình dáng của mặt cong.
Dựa trên tỉ lệ độ lớn giữa các góc, cạnh của các tam giác trên miền tham số, kết hợp với điều kiện sinh nút, bài
viết đã đề xuất kỹ thuật xác định vị trí các nút trong vectơ nút trên miền tham số của B-spline tam giác. Kỹ thuật đƣợc
áp dụng cho cả các nút ở bên trong và ở biên của miền tham số, đồng thời tránh trƣờng hợp cộng tuyến giữa các nút
đƣợc tạo ra. Nhờ đó mặt cong đạt đƣợc đảm bảo độ liên tục, không xuất hiện các vùng gián đoạn, đứt gãy. Kết quả
đƣợc áp dụng cho quá trình tái tạo các B-spline tam giác bậc 2, 3 và 4 từ lƣới tam giác ban đầu bằng phƣơng pháp dịch
chuyển hình học. Chất lƣợng các B-spline tái tạo cải thiện rõ rệt thông qua độ lệch trung bình giảm và tỉ lệ hội tụ tăng.
VI. TÀI LIỆU THAM KHẢO
[1] A. Abbas, A. Nasri, T. Maekawa. “Generating B-spline curves with points, normals and curvature constraints: a
constructive approach”. The Visual Computer, vol.26(6–8), pp.823–829, 2010.
[2] C. Deng, H. Lin. “Progressive and iterative approximation for least squares B-spline curve and surface fitting”.
Computer-Aided Design, vol.47, pp.32–44, 2014.
[3] K. Christopher, Ingram. “A Geometric B-Spline Over the Triangular Domain”. M. S. Mathematics thesis, 2003.
[4] M. Eck, H. Hoppe. “Automatic reconstruction of B-spline surfaces of arbitrary topological type”. In Proceedings
of SIGGRAPH96, ACM Press, pp.325–334, 1996.
[5] G. Farin. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Morgan Kaufmann, San
Mateo, 5th edition, 2002.
[6] P. Fong and H. Seidel. An implementation of triangular B-spline surfaces over arbitrary triangulations. Computer
Aided Geometric Design, 10:267275, 1993.jaj and A. Gillette. Geometric Modeling. 2010.
[7] M. Franssen, R. Veltkamp, and W. Wesselink. Efcient evaluation of triangular B-spline surfaces. Computer Aided
Geometric Design, 17:863877, 2000.
[8] G. Greiner. “Geometric modeling”. Lecture in Winter Term, 2010.
[9] Y. Kineri, M. Wang, H. Lin, T. Maekawa. “B-spline surface fitting by iterative geometric interpolation/
approximation algorithms”. Computer-Aided Design, vol.44(7), pp.697–708, 2012.
[10] M. Liu, B. Li, and et al. Progressive iterative approximation for regularized least square bivariate B-spline surface
fitting. Journal of Computational and Applied Mathematics, 327:175187, 2018.
[11] H. Seidel. Symmetric recursive algorithms for surfaces: B-patches and the de boor algorithm for polynomials over
triangles. Constructive Approximation, 7:257279, 1991.
[12] D. Yoo. “Three-dimensional surface reconstruction of human bone using a B-spline based interpolation approach”,
Computer-Aided Design, vol.43(8), pp.934–947, 2011
IMPROVE QUALITY OF RECONSTRUCTED TRIANGULAR B-SPLINE
BY MODIFYING KNOT-VECTORS
Nga Le Thi Thu1, Khoi Nguyen Tan2, Thuy Nguyen Thanh3
1
Quynhon University, Vietnam
2
Danang University of Science and Technology Danang, Vietnam
3
Vietnam National University Hanoi, Vietnam
lenga248@gmail.com, ntkhoi@dut.udn.vn, nguyenthanhthuy@vnu.edu.vn
ABSTRACT: Reconstruction of smooth surfaces from the 3D meshes has been applied in many fields and has practical significance.
The reconstructed triangular B-spline allows modeling an object surface with arbitrary shape and suit to modify a surface through
its control points. Similar to the position of the control points, the configuration of the knot-vectors also partially affects the result of
the surface reconstruction. This paper proposes a technique for locating knot-vectors over the triangular parametric domain of the
2,3,4 degree B-splines. This approach is that based on the ratio between angles and edges of triangles over the parametric domain,
applied on both inner knots and border knots. The created knots have to satisfy the conditions of knot generation, avoids collinearity
of these knots. This result is applied to reconstruction of triangular B-spline from a 3D mesh based on geometric fitting method. The
experimental examples show that quality of reconstructed triangular B-splines is obviously improved.
Keywords: Reconstruct surface, improve quality, triangular B-spline, knot-vector, modify knot.
nguon tai.lieu . vn
