Tóm tắt Luận án Nghiên cứu phương pháp mô hình hóa mặt cong tham số từ mặt lưới

i

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

LÊ THỊ THU NGA

NGHIÊN CỨU PHƢƠNG PHÁP MÔ HÌNH HÓA

MẶT CONG THAM SỐ TỪ MẶT LƢỚI

Chuyên ngành: Khoa học máy tính

Mã số: 62.48.01.01

TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT

Đà Nẵng - 2018

ii

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Ngƣời hƣớng dẫn khoa học:

1. GS.TS. Nguyễn Thanh Thủy

2. PGS.TS. Nguyễn Tấn Khôi

Phản biện 1: GS.TSKH. Hoàng Văn Kiếm

Phản biện 2: PGS.TS. Lê Mạnh Thạnh

Phản biện 3: PGS.TS. Huỳnh Xuân Hiệp

Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Đại học

Đà Nẵng họp tại: Đại học Đà Nẵng.

Vào hồi 08 giờ 30 ngày 19 tháng 05 năm 2018.

Có thể tìm hiểu luận án tại:

- Thư viện Quốc gia

- Trung tâm Thông tin – Học liệu, Đại học Đà Nẵng

1

MỞ ĐẦU

Mô hình hình học trong không gian 3D đóng vai trò quan trọng

trong 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. Ngày nay, mô hình 3D được sử dụng rộng rãi trong đồ họa máy

tính, hoạt hình, trò chơi 3D, hỗ trợ thiết kế, tái tạo ngược, thực tại ảo và

dùng để mô tả bề mặt của các đối tượng trong nhiều lĩnh vực như: vật

lý, địa chất, y học, hóa học… Những ứng dụng thực tiễn đòi hỏi các mô

hình 3D cần được xây dựng, hiển thị, xử lý nhanh chóng, chính xác và

hiệu quả.

Phần lớn các đối tượng được biểu diễn trên máy tính thông qua mô

hình lưới đa giác. Mô hình này cho phép xử lý nhanh, trực quan và hiệu

quả khi hiển thị, tô bóng bề mặt của đối tượng. Tuy nhiên, lưới đa giác

cũng có những hạn chế như: không có khả năng phân biệt các phần thấy,

khuất của đối tượng; không thể hiện được độ cong rõ rệt; khó có thể xác

định chính xác vị trí của một điểm trên bề mặt đối tượng; không có khả

năng kiểm tra va chạm giữa các đối tượng và khó khăn trong việc tính

toán các đặc tính vật lý…

Trong khi đó, mô hình mặt cong tham số không chỉ cho phép biểu

diễn bề mặt mềm mượt với độ liên tục cao, ổn định, mềm dẻo và điều

chỉnh bề mặt cục bộ thông qua các đỉnh điều khiển; mà còn cung cấp

các phép toán, giải thuật chi tiết để xác định vị trí của điểm bất kỳ trên

bề mặt chính xác và hiệu quả. Nhờ đó, bên cạnh việc hỗ trợ xây dựng

mô hình 3D, tô trát, tạo bóng và 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 có vai trò đắc lực cho

các ứng dụng có khả năng tương tác với bề mặt đối tượng như: mô hình

hóa hình dạng của đố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ệ VR; tái tạo lại bề mặt trong RE; ánh

xạ mẫu nền, kỹ xảo hoạt hình trong CG; mô phỏng bề mặt địa hình, xác

định độ cao, nếp đứt gãy trong GIS; xác định khối lượng, diện tích bề

mặt, thể tích, trọng tâm trong việc 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,…

2

Trong các ứng dụng mô hình hóa, người ta cần khai thác thế mạnh

của cả hai mô hình trên. Do đó, để có thể chuyển đổi qua lại giữa hai mô

hình này nhằm biểu diễn, tương tác trên bề mặt của đối tượng là mối

quan tâm khoa học quan trọng và có nhiều ứng dụng trong các ngành

công nghiệp tiềm năng. Mục tiêu của luận án nhằm xây dựng mô hình

tái tạo mặt cong tham số bậc thấp từ lưới tam giác mô phỏng bề mặt của

đối tượng 3D ban đầu. Kết quả phục vụ cho việc tính toán chi tiết, chính

xác và hỗ trợ khả năng tương tác của đối tượng được mô phỏng trên

máy tính. Từ đó cho phép ánh xạ mẫu nền, phân tích sớm và dễ dàng

xác định các đặc tính vật lý của bề mặt, hỗ trợ trong lập trình gia công,

mô phỏng, phát hiện va chạm, tạo các biến dạng,... Đây cũng là nhu cầu

cấp thiết mang tính thực tiễn và có nhiều ứng dụng, đặc biệt là trong

lĩnh vực thiết kế và tạo mẫu mã sản phẩm, công nghệ thực tại ảo và

công nghệ tái tạo ngược.

Với mục đích tái tạo mặt cong tham số bậc thấp xấp xỉ với các điểm

dữ liệu của lưới tam giác mô phỏng bề mặt đối tượng 3D, luận án đề

xuất hướng nghiên cứu sử dụng lược đồ tái hợp mảnh nhằm xây dựng

lưới điều khiển để giảm bậc của mặt cong tham số cần tái tạo, đồng thời

áp dụng phương pháp xấp xỉ hình học cục bộ nhằm tránh giải các hệ

phương trình tuyến tính.

Các đóng góp chính của luận án về mặt khoa học:

- Đề xuất giải pháp sử dụng lược đồ tái hợp mảnh nhằm đơn giản lưới

tam giác ban đầu và sử dụng lưới thô kết quả như là lưới điều khiển

của mặt cong cần tái tạo. Do đó, mặt cong tham số tái tạo được có

bậc thấp hơn so với các phương pháp trước đó là sử dụng trực tiếp

lưới ban đầu như lưới điều khiển;

- Đề xuất giải pháp xây dựng các vector nút trên miền tham số tam

giác của mặt cong, từ đó áp dụng để dựng các mặt cong tái tạo;

- Đề xuất phương pháp xấp xỉ hình học cục bộ để dịch chuyển mặt

cong tham số hội tụ dần về lưới tam giác ban đầu, tránh việc giải hệ

phương trình phức tạp. Chứng minh được tính hội tụ của giải thuật

xấp xỉ hình học đề xuất;

3

- Đề xuất mô hình tái tạo mặt cong tham số có bậc thấp từ lưới tam

giác dựa trên lược đồ tái hợp mảnh và phương pháp xấp xỉ hình học,

đồng thời mô phỏng thực nghiệm để thấy được tính khả thi của mô

hình đề xuất.

Kết quả đạt được của luận án là tái tạo các mặt cong tham số có bậc

thấp từ lưới tam giác mô phỏng bề mặt của đối tượng thực, cụ thể là các

mặt cong tham số Bézier tam giác, B-patch và B-spline tam giác. Hầu

hết các mô hình hiện tại thường được biểu diễn là lưới tam giác, nhờ

tính đa hình dạng và mềm dẻo của nó. Mặt khác, các mặt cong thường

dùng trong thiết kế hình học là các mặt cong tham số bậc thấp. Do đó,

kết quả nghiên cứu này có ý nghĩa thực tiễn và có thể được ứng dụng

trong nhiều lĩnh vực như: hỗ trợ thiết kế, tạo mẫu mã sản phẩm, tái tạo

ngược và thực tại ảo; phân tích phần tử hữu hạn, tính toán chính xác các

đặc tính vật lý của bề mặt; ứng dụng trong nén dữ liệu 3D; trao đổi dữ

liệu 3D trên môi trường mạng không dây băng thông hẹp và trên các

thiết bị di động.

CHƢƠNG 1

SƠ LƢỢC VỀ TÁI TẠO MẶT CONG

Chương này trình bày tổng quan về các mô hình biểu diễn bề mặt

của đối tượng 3D, các phương pháp tái tạo mặt cong, phân tích và so

sánh các nghiên cứu liên quan đến tái tạo mặt cong trơn mềm từ mô

hình lưới; từ đó đề xuất hướng nghiên cứu của luận án.

1.1. Các mô hình biểu diễn bề mặt đối tƣợng

Các mô hình hình học trong không gian 3D không những được sử

dụng rộng rãi trong đồ họa máy tính, mà còn đóng vai trò quan trọng

trong công nghiệp và khoa học với nhiều mục đích khác nhau.

Về cơ bản, các mô hình hình học 3D, dùng để biểu diễn bề mặt của

đối tượng trên máy tính, có thể chia thành ba loại chính:

- Mô hình lưới;

- Mô hình phân mảnh;

- Mô hình mặt cong tham số.

4

1.2. Chuyển đổi giữa các mô hình

Mô hình lưới và mô hình tham số đều có những ưu và nhược điểm

nhất định, có nhiều ứng dụng thực tiễn và có mối liên hệ mật thiết lẫn

nhau. Trong quá trình sử dụng, để tận dụng thế mạnh của cả hai mô hình

này, việc chuyển đổi qua lại giữa hai dạng biểu diễn cho cùng một đối

tượng 3D là nhu cầu thiết thực và có nhiều ứng dụng trong thực tế. Việc

chuyến đổi cho phép biểu diễn đối tượng trên nhiều nền tảng khác nhau,

phục vụ cho nhu cầu mô phỏng, tính toán, khả năng tương tác của đối

tượng, phân tích các đặc tính vật lý của bề mặt, hỗ trợ lập trình gia công,

phát hiện va chạm, tạo biến dạng,...

1.3. Tái tạo mặt cong

Tái tạo mặt cong trơn mềm từ mô hình lưới 3D được ứng dụng

nhiều trong khoa học, công nghệ, giải trí,… và có nhiều nghiên cứu

trong những năm gần đây. Hầu hết, các nghiên cứu về tái tạo mặt cong

trơn thường tập trung vào nội suy hoặc xấp xỉ các mặt cong tham số

hoặc mặt cong giới hạn phân mảnh về lưới đa giác gồm các điểm dữ liệu

3D ban đầu. Vì vậy, các mặt cong kết quả thu được thường là 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, NURBS,…

1.4. Các nghiên cứu liên quan

Dựa vào phương pháp tái tạo mặt cong, các nghiên cứu liên quan

đến tái tạo mặt cong trơn mềm từ lưới 3D có thể chia làm ba nhóm sau:

- Tái tạo mặt cong bằng phương pháp nội suy;

- Tái tạo mặt cong bằng phương pháp xấp xỉ;

- Tái tạo mặt cong bằng phương pháp hình học.

Hạn chế của phương pháp nội suy là phải giải các hệ phương trình

tuyến tính để nội suy các điểm tính toán, điều này dẫn đến phức tạp và

chi phí lớn. Mặt khác, mặt cong tái tạo được xuất hiện những phần mấp

mô ngoài ý muốn ở những mặt đa thức bậc cao. Với phương pháp xấp

5

xỉ, mặt cong tái tạo được tiệm cận theo hình dáng của lưới dữ liệu, chất

lượng bề mặt tốt hơn so với mặt cong nội suy.

Đa số các nghiên cứu dừng lại ở việc xây dựng mặt cong trơn từ

lưới tứ giác. Trong khi đó, các bề mặt của đối tượng trong thực tế lại có

dạng hình học bất kỳ. Hướng tiếp cận phổ biến hiện nay là biến đổi mặt

lưới tam giác thành các mặt lưới tứ giác và tái tạo các mặt cong từ các

lưới tứ giác này.

Vì quá trình tái tạo phải đảm bảo chất lượng bề mặt, tối ưu bộ nhớ

và thời gian tái tạo ngắn nhằm phục vụ cho các bước mô phỏng sau này;

do đó, sử dụng phương pháp hình học để tái tạo mặt cong tham số từ

lưới tam giác và giảm bậc của mặt cong tái tạo được là tiếp cận mà luận

án nhắm tới.

1.5. Hƣớng nghiên cứu đề xuất

Trên cơ sở tìm hiểu, tổng hợp, phân tích các kiến thức và các nghiên

cứu liên quan; tận dụng các ưu điểm của mô hình lưới tam giác, mặt

cong trên miền tham số tam giác, cũng như lợi ích của tái hợp mảnh

nhằm giảm bậc của mặt cong tham số được tái tạo; các phương pháp

chuyển đổi một lưới đa giác sang mặt cong trơn, luận án đề xuất giải

pháp nhằm mô hình hóa mặt cong tham số bậc thấp từ lưới tam giác dựa

trên lược đồ tái hợp mảnh và phương pháp xấp xỉ hình học cục bộ.

Bằng cách sử dụng lược đồ tái hợp mảnh để đơn giản lưới ban đầu,

từ đó dùng các điểm của lưới thô này như các đỉnh điều khiển của mặt

cong tham số, nhờ vậy mà mặt cong tham số tái tạo sẽ có bậc giảm hơn

so với việc sử dụng lưới gốc ban đầu như lưới điều khiển. Kết quả, mặt

cong tham số thu được trơn mượt, tránh hiện tượng nhấp nhô ngoài ý

muốn của các mặt cong tham số bậc cao.

Bên cạnh đó, mô hình đề xuất sử dụng phương pháp xấp xỉ hình học

cục bộ để dịch chuyển mặt cong tham số hội tụ dần về các điểm dữ liệu

của lưới tam giác ban đầu thông qua một số bước lặp, điều chỉnh việc

xấp xỉ mặt cong một cách trực quan và chính xác cho đến khi mặt cong

đi qua hầu hết các điểm dữ liệu ban đầu.

6

1.6. Kết luận chƣơng 1

Trên cơ sở tìm hiểu về ưu điểm của các mô hình hình học 3D và

phương pháp hình học, luận án đã đề xuất hướng nghiên cứu nhằm tái

táo mặt cong tham số bậc thấp dựa trên lược đồ tái hợp mảnh và phương

pháp xấp xỉ hình học cục bộ.

Trong các chương 2 và 3, luận án đi sâu vào trình bày và xử lý các

đối tượng liên quan đến hướng nghiên cứu, cụ thể như: phân mảnh và

tái hợp mảnh trên lưới tam giác, mặt cong trên miền tham số tam giác;

từ đó đề xuất phương pháp tạo lưới điều khiển dựa trên tái hợp mảnh,

đưa ra các giải thuật dựng mặt cong trên miền tham số tam giác; làm cơ

sở cho việc xây dựng mô hình tái tạo mặt cong tham số từ lưới tam giác

được đề xuất trong chương 4.

CHƢƠNG 2

XÂY DỰNG LƢỚI ĐIỀU KHIỂN MẶT CONG THAM SỐ

DÙNG TÁI HỢP MẢNH

Nhằm tái tạo mặt cong tham số bậc thấp từ lưới tam giác, chương

này trình bày về lược đồ phân mảnh lưới, so sánh các lược đồ để xác

định lược đồ phân mảnh phù hợp với hướng tiếp cận. Từ đó xác định

lược đồ tái hợp mảnh trên lưới tam giác và đề xuất phương pháp tạo

lưới điều khiển của mặt cong tham số tái tạo dựa trên lược đồ tái hợp

mảnh.

2.1. Phân mảnh trên lƣới tam giác

Phân mảnh lưới cho phép biểu diễn bề mặt của đối tượng thực có

hình dạng bất kỳ với nhiều mức phân giải khác nhau. Sự xuất hiện của

lưới phân mảnh trong lĩnh vực mô phỏng bề mặt đã tạo một bước đột

phá mới trong công nghệ làm phim, trò chơi 3D,… Đối với những ứng

dụng chỉ yêu cầu biểu diễn bề mặt mềm mịn thì lưới phân mảnh là lựa

chọn phù hợp để thay thế cho mặt cong tham số.

Nhận thấy phân mảnh Loop có các ưu điểm vượt trội. Đây là phân

mảnh xấp xỉ nên lưới tam giác thu được sau phân mảnh sẽ có xu hướng

7

co lại so với các lưới ở những bước phân mảnh trước đó. Điều này cũng

có nghĩa là nếu áp dụng tái hợp mảnh cho một lưới tam giác thì lưới thu

được sau mỗi bước tái hợp mảnh sẽ có xu hướng phồng lên và trở thành

bao lồi của lưới tam giác này. Đây cũng chính là phát hiện quan trọng để

chọn tái hợp phân mảnh Loop trong hướng tiếp cận của luận án, nhằm

sử dụng lưới sau khi được tái hợp mảnh làm lưới điều khiển của mặt

cong tham số tái tạo.

Phân mảnh Loop là một lược đồ phân mảnh chèn đỉnh xấp xỉ dựa

trên cơ sở mặt cong spline trên miền tham số tam giác. Phân mảnh này

cho phép làm mịn lưới tam giác bất kỳ và sinh ra mặt cong giới hạn

spline liên lục C²trên miền lưới đều, loại trừ tại vị trí của các đỉnh đặc

biệt đạt liên tục C¹. Trong phân mảnh Loop, sau bước phân mảnh thứ i,

các đỉnh của lưới tam giác Mⁱđược chia thành hai loại:

- Điểm đỉnh: là các đỉnh cũ được hiệu chỉnh lại vị trí;

- Điểm cạnh: là các đỉnh mới được chèn thêm vào cạnh.

Khi đó, vị trí của điểm đỉnh p^{i + 1}sau mỗi bước áp dụng phân mảnh

Loop được xác định như sau:

l

p^i1 pⁱ pⁱ

(2.1)



j

j1

p₁^i1p₂^i1p^i1

Vị trí các điểm cạnh

,

…

sau mỗi bước phân mảnh

k

Loop được xác định như sau:

3

1

pⁱ_j^1 pⁱ pⁱ_j pⁱ_j1 pⁱ_j1

(2.2)

8

với j=1..l và l là số bậc tương ứng của đỉnh pⁱ.

2.2. Tái hợp mảnh trên lƣới tam giác

Tái hợp mảnh cho phép chuyển một lưới mịn thành lưới thô hơn, ít

dữ liệu hơn nhưng vẫn không mất đi dạng hình học và cấu trúc hình học

của lưới, đồng thời có thể phục hồi lại hoàn toàn bằng cách sử dụng

lược đồ phân mảnh. Điều này cho phép tiết kiệm không gian lưu trữ,

giảm băng thông, phù hợp cho các ứng dụng đồ họa trên thiết bị di động

và biểu diễn đa mức phụ thuộc vào điểm quan sát.

8

Đặc biệt, với phân mảnh xấp xỉ Loop, nếu áp dụng tái hợp mảnh,

lưới thu được sẽ có số điểm dữ liệu giảm và có xu hướng phồng lên so

với lưới trước khi tái hợp mảnh. Do đó, lưới sau tái hợp mảnh phù hợp

cho việc mô hình hóa mặt cong tham số khi sử dụng lưới này như lưới

điều khiển, như bao lồi của mặt cong, tránh làm việc trên đa thức bậc

cao, giảm mấp mô ngoài mong muốn của mặt cong tham số thu được.

Gọi  là trọng số của đỉnh p^{i + 1}và  là trọng số của các đỉnh lân

cận, ta có công thức để xác định pⁱnhư sau:

l

pⁱ .p^i1 . p^i1

(2.3)



j

j1

với

5

 1

 

và  

3

8 3







(2.4)

l  







8

2.3. Sử dụng tái hợp mảnh tạo lƣới điều khiển của mặt cong

Để tái tạo mặt cong tham số bậc thấp từ lưới tam giác, hướng tiếp

cận của luận án dựa trên tái hợp mảnh và sử dụng lược đồ lưới tái hợp

mảnh để tạo lưới điều khiển của mặt cong. Các mặt cong trên miền tham

số tam giác cần tái tạo cụ thể là Bézier tam giác, B-patch và B-spline

tam giác. Do đó, yêu cầu lưới tam giác ban đầu phải được hiệu chỉnh

cho phù hợp với điều kiện của lưới phân mảnh và lưới điều khiển của

mặt cong trên miền tham số tam giác.

Để thỏa các các điều kiện này, luận án đề xuất quá trình xây dựng

lưới điều khiển của mặt cong tham số từ lưới tam giác như sau:

- Bước 1: Hiệu chỉnh phù hợp với lưới điều khiển của mặt cong;

- Bước 2: Cập nhật cấu trúc lưới phù hợp với lưới phân mảnh;

- Bước 3: Đơn giản lưới dùng lược đồ tái hợp mảnh Loop.

9

Hình 2.34. Lưới gốc (a) và lưới kết quả sau 1, 2, 3 bước

tái hợp mảnh Loop (b,c,d)

Hình 2.34 minh họa các kết quả thu được sau khi áp dụng lược đồ

tái hợp mảnh Loop trên lưới tam giác mô tả bề mặt của các đối tượng

baseball cap, mountain và pawn. Từ lưới mịn ban đầu (Hình 2.34a),

bằng cách áp dụng lược đồ tái hợp mảnh Loop, sau i=1, 2, 3 bước tái

hợp mảnh (Hình 2.34bcd), lưới gốc đã được “thô hóa” với kích thước

giảm mạnh theo cấp số nhân sau mỗi bước tái hợp mảnh. Cụ thể, số mặt

10

giảm chỉ còn 1/4 so với lưới ở bước tái hợp mảnh trước đó. Lưới thô thu

được có kích thước nhỏ, số đỉnh, mặt và cạnh giảm hẳn nhưng vẫn đảm

bảo dạng và cấu trúc hình học của lưới. Đồng thời vẫn có thể khôi phục

trở lại lưới mịn ban đầu bằng cách áp dụng lược đồ phân mảnh Loop.

Với kết quả này, luận án sẽ sử dụng lưới sau khi tái hợp mảnh như

lưới điều khiển của mặt cong trong quá trình tái tạo mặt cong trên miền

tham số tam giác được trình bày trong chương 4.

2.4. Kết luận chƣơng 2

Trong chương này, luận án đã tìm hiểu, phân tích, so sánh và cài đặt

thử nghiệm để thấy được lược đồ phân mảnh Loop có nhiều ưu điểm và

thích hợp cho sử dụng tái hợp mảnh Loop nhằm thô hóa lưới điều khiển.

Từ đó đề xuất thuật toán đơn giản lưới dựa trên tái hợp mảnh nhằm sử

dụng lưới thô này như lưới điều khiển của mặt cong tham số, giảm bậc

của mặt cong tham số tái tạo. Để lưới tam giác ban đầu thỏa điều kiện

của lưới điều khiển (đáp ứng yêu cầu về số đỉnh điều khiển) và lưới

phân mảnh (đáp ứng yêu cầu về cấu trúc dữ liệu), luận án cũng đã đề

xuất thuật toán hiệu chỉnh lưới và cập nhật cấu trúc dữ liệu của lưới ban

đầu trước khi tiến hành tái hợp mảnh Loop để đơn giản lưới. Kết quả

phân tích và đạt được của chương này sẽ được sử dụng để dựng các mặt

cong tham số Bézier tam giác, B-patch và B-spline tam giác trong

chương 3 tiếp theo.

CHƢƠNG 3

BIỂU DIỄN MẶT CONG TRÊN MIỀN THAM SỐ TAM GIÁC

Nội dung chương tập trung trình bày về biểu diễn, tính chất hình

học và cách xác định điểm thuộc mặt cong tham số tam giác. Cách xác

định vector nút trên miền tham số của mặt cong đề xuất ở cuối chương.

3.1. Một số khái niệm

Phần này trình bày một số khái niệm toán học liên quan đến định

nghĩa, biểu diễn mặt cong tham số như: tọa độ tâm, dạng cực, bao lồi

bán mở,...

11

3.2. Mặt cong tham số tam giác

Mặt cong tham số tam giác với lưới điều khiển là lưới tam giác, đây

là dạng lưới phổ biến và cho phép biểu diễn bề mặt của đối tượng có

dạng bất kỳ. Do đó mặt cong này có nhiều ưu điểm hơn trong việc mô

phỏng bề mặt đối tượng 3D trên máy tính. Mặt khác đa thức Bernstein

trên miền tham số tam giác phức tạp hơn đa thức Bernstein một biến và

B-spline tứ giác nên mặt cong trên miền tham số tam giác vẫn đang là

vấn đề đang được quan tâm nghiên cứu và ứng dụng. Mục đích của luận

án là tái tạo mặt cong tham số từ lưới tam giác, nên phần tiếp theo của

luận án sẽ tập trung trình bày chi tiết về dạng mặt cong này.

Mặt cong Bézier tam giác là mặt cong tham số với hàm đa thức theo

tham số u được định nghĩa trên miền tham số có dạng tam giác. Bậc của

đa thức phụ thuộc vào số đỉnh điều khiển được dùng để định nghĩa mặt

cong. Bézier tam giác không đi qua các đỉnh điều khiển mà nằm trong

bao lồi được tạo bởi các đỉnh này. Đồng thời, nhờ các đỉnh điều khiển

mà hình dạng của mặt cong có thể hiệu chỉnh một cách dễ dàng, đây

cũng chính là lý do mà mặt cong Bézier được sử dụng phổ biến.

Mặt cong B-patch được xây dựng dựa trên ý tưởng “kéo nút” tại 3

góc trên miền tham số của mặt cong Bézier tam giác. Tập các nút ứng

với mỗi góc của miền tham số được xem như là một vector nút. Bên

cạnh lưới điều khiển, các vector nút đóng vai trò quan trọng trong việc

điều chỉnh hình dáng của mặt cong.

Mặt cong B-spline tam giác, hay còn gọi là DMS-splines, là sự kết

hợp trơn mềm toàn cục của mặt cong Splines đơn hình và sự điều khiển

cục bộ của mặt cong B-patch. 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 liên tục C^n-1tự động mà

không cần phải kết nối giữa các mảnh cong.

3.3. Xác định các vector nút trên miền tham số tam giác

Đối với mặt cong B-patch và B-spline tam giác, 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 ảnh

hưởng bởi cấu hình của các vector nút trên miền tham số. Luận án đề

12

xuất cách xác định vị trí của các nút trong vector nút trên miền tham số

của các mặt cong bậc 2, 3 và 4. Từ đó hỗ trợ cho việc dựng các mặt

cong trên miền tham số tam giác và điều chỉnh các vector nút trong quá

trình xấp xỉ hình học được sử dụng trong mô hình tái tạo mặt cong tham

số đề xuất ở chương 4 của luận án.

3.4. Kết luận chƣơng 3

Dựa trên mô hình tham số, đặc biệt là các mặt cong tham số tam

giác, luận án nhận thấy các mặt cong Bézier tam giác, B-patch và B-

spline tam giác có nhiều ưu điểm, phù hợp cho cho mục đích tái tạo bề

mặt có hình dạng bất kỳ và có thể điều chỉnh hình dạng thông qua các

đỉnh điều khiển. Do đó, luận án sẽ sử dụng các mặt cong này như mặt

cong tái tạo nhận được. Hình dạng của mặt cong không chỉ chịu ảnh

hưởng bởi vị trí các đỉnh điều khiển, mà còn phụ thuộc vào vị trí các nút

trong vector nút trên miền tham số. Do đó, đóng góp của luận án trong

chương này là đề xuất cách xác định vị trí các nút trong vector nút, làm

cơ sở cho việc dựng mặt cong và điều chỉnh hình dạng của mặt cong

trong quá trình tái tạo, theo mô hình đề xuất ở chương 4 của luận án.

CHƢƠNG 4

TÁI TẠO MẶT CONG THAM SỐ

DỰA TRÊN LƢỢC ĐỒ TÁI HỢP MẢNH

Dựa trên các kết quả đạt được ở chương 2 và 3, trong chương này,

luận án đề xuất mô hình tái tạo mặt cong tham số từ lưới tam giác dựa

trên hướng tiếp cận sử dụng lược đồ tái hợp mảnh Loop, cùng với áp

dụng phương pháp xấp xỉ hình học cục bộ. Các mặt cong tham số Bézier

tam giác, B-patch và B-spline tam giác được tái tạo có bậc thấp và xấp

xỉ với lưới dữ liệu ban đầu.

4.1. Phƣơng pháp tái tạo mặt cong tham số

4.1.1. Đặt vấn đề

Lưới tam giác được dùng phổ biến để mô phỏng các đối tượng hình

học 3D trên máy tính vì nó cho phép biểu diễn bề mặt có hình dạng bất kỳ

13

với độ dốc thay đổi, tốc độ xử lý nhanh. Do đó, luận án tập trung vào tái

tạo các mặt cong tham số từ các điểm dữ liệu của lưới tam giác đã cho.

Phát biểu bài toán: Cho lưới tam giác M được tạo bởi m điểm dữ

liệu p_j|_{j = 1..m}R³. Tái tạo mặt cong S trên miền tham số tam giác xấp xỉ

với lưới M đã cho.

4.1.2. Mô hình tái tạo mặt cong tham số đề xuất

Dựa vào lược đồ tái hợp mảnh Loop trên lưới tam giác và phương

pháp xấp xỉ hình học, luận án đề xuất mô hình tái tạo mặt cong tham số

bậc thấp S (cụ thể là các mặt cong Bézier tam giác, B-patch, B-spline

tam giác) từ lưới tam giác M (Hình 4.1). Mô hình này bao gồm các

bước chính như sau:

- Bước 1: Hiệu chỉnh lưới tam giác. Từ lưới tam giác M ban đầu, lưới

này sẽ được hiệu chỉnh cho phù hợp với lưới điều khiển. Việc hiệu

chỉnh thường là bổ sung thêm một vài đỉnh để đủ số điểm cần thiết

của lưới điều khiển mặt cong trên miền tham số tam giác. Ngoài ra,

để tăng chất lượng lưới, các mặt tam giác yếu của lưới này cũng

được đảo cạnh cho thỏa điều kiện Delaunay;

- Bước 2: Cập nhật cấu trúc dữ liệu lưới. Lưới M được cập nhật lại cấu

trúc dữ liệu để trở thành lưới phân mảnh M⁰.

- Bước 3: Đơn giản lưới dùng tái hợp mảnh. Bằng cách áp dụng lược

đồ tái hợp mảnh Loop, lưới tam giác phân mảnh M⁰sẽ được tái hợp

mảnh sau i bước để trở thành lưới thô Mⁱ. Như vậy, lưới Mⁱchính là

lưới M⁰được thô hóa với kích thước giảm mạnh, số mặt chỉ còn lại

1/4 so với lưới M^i-1;

- Bước 4: Dựng mặt cong tham số. Lưới thô Mⁱsẽ được dùng như là

lưới điều khiển để xây dựng mặt cong tham số Sⁱ. Do đó mà mặt

cong tham số tái tạo được sẽ có bậc thấp hơn so với việc dùng lưới

ban đầu như lưới điều khiển;

- Bước 5: Xấp xỉ hình học. Thực hiện dich chuyển hình học mặt cong

tham số Sⁱbằng cách cập nhật lại vị trí của các đỉnh điều khiển. Sau

mỗi bước dịch chuyển, mặt cong Sⁱsẽ được dịch dần về các điểm dữ

liệu của lưới tam giác M ban đầu.

14

Hình 4.1.Mô hình tái tạo mặt cong tham số dựa trên lược đồ tái hợp mảnh

Trong mô hình đề xuất có ba giai đoạn chính:

- Giai đoạn 1: Xây dựng lưới điều khiển. Gồm các bước 1, 2 và 3. Mục

đích của giai đoạn 1 là xử lý lưới tam giác ban đầu và tạo lưới điều

khiển của mặt cong tham số. Các bước của giai đoạn này đã được

trình bày chi tiết trong mục 2.3 ở chương 2 của luận án;

- Giai đoạn 2: Dựng mặt cong tham số. Mục đích của giai đoạn này là

dựng mặt cong tham số trên miền tam giác với lưới điều khiển của

mặt cong là lưới thu được ở giai đoạn 1. Giai đoạn 2 ứng với bước 4

15

của mô hình đề xuất. Công việc của giai đoạn 2 cũng đã được trình

bày ở mục 3.3 thuộc chương 3 của luận án;

- Giai đoạn 3: Xấp xỉ hình học cục bộ. Tại mỗi bước dịch chuyển, giai

đoạn này sẽ sinh ra một mặt cong tham số. Mặt cong này được so

sánh độ lệch cục bộ trên từng điểm dữ liệu để xác định độ chính xác

trong dịch chuyển, đồng thời đưa mặt cong dần hội tụ về lưới dữ

liệu ban đầu. Đây cũng chính là bước 5 của mô hình đề xuất và sẽ

được tiếp tục làm rõ trong chương này.

4.1.3. Phương pháp xấp xỉ hình học

Gọi M⁰, Mⁱvà Sⁱlà các lưới và mặt cong tham số thu được sau khi

thực hiện xong bước 4 trong mô hình đề xuất ở Hình 4.1,  là dung sai.

Phương pháp xấp xỉ hình học cục bộ đề xuất được biểu diễn trên sơ đồ

trong Hình 4.3.

Hình 4.3. Phương pháp xấp xỉ hình học

16

Trong quá trình xấp xỉ hình học, một chuỗi các lưới tam giác M*

được tạo ra và các lưới này được được thô hóa thành lưới Mⁱ. Tương

ứng, một chuỗi các mặt cong tham số lần lượt cũng được sinh ra. Các

mặt cong này có xu hướng hội tụ dần về lưới ban đầu. Quá trình dịch

ⁱ

chuyển dừng khi lỗi trung bình _avgbé hơn dung sai . Cuối cùng, mặt

cong tham số tái tạo được sẽ xấp xỉ với các điểm dữ liệu ban đầu với lỗi

trung bình nhỏ nhất.

4.1.4. Sự hội tụ của phương pháp xấp xỉ hình học

Dựa trên phương pháp xấp xỉ hình học đề xuất, phần này phân tích

sự hội tụ của mặt cong tham số tái tạo được so với các điểm dữ liệu ban

đầu theo phương pháp xấp xỉ hình học đề xuất.

4.2. Tái tạo mặt cong Bézier tam giác

Dựa trên mô hình đề xuất, mục này đưa ra giải thuật xấp xỉ hình học

để tái tạo Bézier tam giác bậc thấp cùng với một số kết quả thực nghiệm

để thấy được tính khả thi của phương pháp đề xuất.

4.3. Tái tạo mặt cong B-patch

Dựa trên mô hình đề xuất, mục này đưa ra giải thuật xấp xỉ hình học

để tái tạo B-patch bậc thấp cùng với một số kết quả thực nghiệm để thấy

được tính khả thi của phương pháp đề xuất.

4.4. Tái tạo mặt cong B-spline tam giác

Dựa trên mô hình đề xuất, mục này đưa ra giải thuật xấp xỉ hình học

để tái tạo B-spline tam giác bậc thấp cùng với một số kết quả thực

nghiệm để thấy được tính khả thi của phương pháp đề xuất.

4.5. Đánh giá chung kết quả thực nghiệm tái tạo mặt cong

Thông tin chi tiết về lưới ban đầu dùng để thử nghiệm và tương ứng

là các dạng mặt cong tham số Bézier tam giác, B-patch và B-spline tam

giác tái tạo được dựa trên mô hình đề xuất được thể hiện trong Bảng 4.5.

17

Bảng 4.5. Các mô hình thực nghiệm

và mặt cong trên miền tham số tam giác tái tạo được

Hình 4.15. Tái tạo các mặt cong tham số Bézier tam giác, B-patch và B-spline

tam giác: (a) lưới gốc, (b,c,d) các mặt cong đạt được

so với lưới gốc sau k = 1,5,7 bước dịch chuyển.

18

Hình 4.15 minh họa các lưới ban đầu và các mặt cong trên miền

tham số đạt được so với lưới gốc sau k = 1,5,7 bước dịch chuyển trong

giải thuật xấp xỉ hình học. Nhận thấy sau bước dịch chuyển đầu liên k =

1, độ chênh giữa mặt cong tham số thu được và lưới gốc còn khá lớn,

đặc biệt là phần biên của mặt cong và đường biên của lưới gốc. Tuy

nhiên sau k = 5,7 bước dịch chuyển, phần biên của mặt cong được dịch

dần về các biên của lưới gốc. Đồng thời các phần còn lại của mặt cong

như được “dãn ra” và dịch dần về các điểm dữ liệu của lưới ban đầu. Sự

chênh lệch của mặt cong thu được so với lưới gốc cũng giảm ở bước

dịch chuyển k = 5,7. Bằng cách áp dụng i = 2 lần tái hợp mảnh, các mặt

cong trên miền tham số tam giác thu được sau quá trình tái tạo có bậc

thấp hơn nhiều so với việc sử dụng lưới ban đầu như lưới điều khiển.

Thời gian tái tạo rất ngắn, mặc dù phải xác định các Spline đơn hình để

tính tọa độ của mỗi điểm trên mặt cong, nhưng chỉ mất khoảng 1 phút

để tái tạo B-spline tam giác.

Bảng 4.6 Các thông số về độ lệch và độ hội tụ

Bảng 4.6 thể hiện chi tiết các thông số về độ lệch và độ hội tụ đạt

được trong quá trình tái tạo thông qua k=10 bước dịch chuyển đầu tiên.

Nhận thấy rằng các độ lệch lớn nhất _maxvà độ lệch trung bình _avgtỉ lệ