Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ép\\
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT&TT Nguyễn Thanh Hải B-SPLINE VÀ ỨNG DỤNG TRONG ĐỒ HỌA MÁY TÍNH
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỤC LỤC
MỞ ĐẦU 1
1. Đặt vấn đề 1
2. Đối tượng và phạm vi nghiên cứu 1
3. Hướng nghiên cứu của đề tài 1
4. Những nội dung nghiên cứu chính 2
5. Phương pháp nghiên cứu 2
6. Ý nghĩa khoa học của đề tài 2
Chƣơng 1 Lý thuyết mô hình hóa hình học 3
1.1. Cơ sở của mô hình hóa hình học 3
1.1.1. Các phép biến đổi tọa độ 2D 3
1.1.2. Phép biến đổi đồng nhất 4
1.1.3. Các phép biến đổi tọa độ 3D 4
1.1.4. Phép ánh xạ 6
1.1.5. Khung tọa độ 8
1.2. Đường cong – Curve 9
1.3. Mặt cong - Surface 13
1.3.1. Biểu diễn mặt cong 13
1.3.2. Mô hình hóa các mặt cong 14
Chƣơng 2 Đƣờng cong, mặt cong B-Spline 16
2.1. Thuật toán Casteljau 16
2.2. Đường cong và mặt cong Bezier 18
2.2.1. Đường cong Bezier 19
2.2.2. Mặt cong Bezier 23
2.3. Đường cong B-Spline 25
2.3.1. Đánh giá đường cong Bezier 25
Hình 1.5 Mô hình mặt tròn xoay 15
Hình 1.6: Mô hình mặt trượt 15
Hình 2.1: Thuật toán Casteljau cho ba điểm 17
Hình 2.2: Đường cong Bezier bậc 1, 2, 3 20
Hình 2.3: Mặt cong Bezier 25
Hình 2.4: Các thành phần của đa thức riêng phần 26
Hình 2.5: Đường cong B-Spline 29
Hình 2.6: Mặt cong B-Spline 34
Hình 3.1 Phép nối điểm và mịn hóa đường cong 37
Hình 3.2 Xác định đa giác kiểm soát của đường cong B-Spline qua một số
điểm đã biết nằm trên đường cong. 38
Hình 3.3: Biểu diễn quả táo 44
Hình 3.4: Biểu diễn lọ hoa 45
Hình 3.5: Biểu diễn máy bay 49
Hình 3.6: Giao diện chương trình chính 50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
DANH SÁCH CÁC BẢNG
Bảng 1.1: Phép quay 3D quanh các trục tọa độ 5
Bảng 2.1: Vector nút đều 31
Bảng 2.2: Vector nút của đường cong B-Spline bậc 2,3,4 không tuần hoàn 32
nhiều lĩnh vực khác nhau từ khoa học, công nghệ, y tế, kỹ thuật đến giải trí
Đồ họa máy tính phát triển dựa trên các kết quả của hình học họa hình,
hình học vi phân cùng với nhiều kết quả toán học khác đặc biệt bao gồm đại
số và giải tích. Hiện nay, với sự phát triển của phần cứng máy tính, đồ họa
cũng phát triển nhanh hơn, tuy vậy nền tảng của nó vẫn là cơ sở mô hình hóa
hình học. Có nhiều bài toán đặt ra trong đồ họa máy tính. Một trong những
bài toán cơ bản của nó là xử lý các đường cong và mặt cong.
B-Splines là một dạng đường cong và mặt cong trong mô hình hóa hình
học đã được nhiều tác giả trên thế giới nghiên cứu.
Đề tài này tìm hiểu về B-Splines, từ đó đưa ra một ứng dụng trong đồ
họa máy tính, cụ thể là ứng dụng trong bài toán mô hình hóa vật thể 3D.
2. Đối tƣợng và phạm vi nghiên cứu
Đối tượng: Cơ sở mô hình hóa hình học, B-Splines, Ứng dụng B-
Splines trong đồ họa.
Phạm vi: Đề tài tập trung tìm hiểu lý thuyết về B-Splines của mô hình
hóa hình học.
3. Hƣớng nghiên cứu của đề tài
Tổng hợp một số kết quả cơ bản của hình học vi phân và phép biến
đổi hình học sử dụng trong mô hình hóa hình học. Trong đó tập trung
chủ yếu đến các lý thuyết về đường cong, mặt cong và các phép biến
đổi tọa độ.
Tìm hiểu lý thuyết mô hình hóa các thực thể hình học bao gồm đường
cong và mặt cong.
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Tìm hiểu lý thuyết B-Splines.
Từ những kết quả lý thuyết B-Splines, ứng dụng vào bài toán mô hình
hóa vật thể 3D.
4. Những nội dung nghiên cứu chính
Tìm hiểu những kiến thức tổng quan về mô hình hóa hình học.
độ (x', y') của điểm P' tương ứng với vector dịch chuyển t(t
x
, t
y
) (Hình 1.1a),
hệ số tỷ lệ s(s
x
, s
y
) (Hình 1.1b); góc xoay θ ngược chiều quay kim đồng hồ
(Hình 1.1c) được xác định như sau:
x' = x + t
x
; y' = y + t
y
(1.1)
x' = s
x
x; y' = s
y
y (1.2)
x' = xcosθ – ysinθ; y' = xsinθ + ycosθ (1.3)
P(x,y)
P
’
(x’,y’)
r
y
x
o
α
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1.1.2. Phép biến đổi đồng nhất
Biểu diễn điểm dưới dạng tọa độ đồng nhất cho phép đơn giản hóa và
thống nhất hóa việc biểu diễn các phép biến đổi hình học như là phép nhân
ma trận.
Theo tọa độ đồng nhất, điểm trong không gian n chiều được ánh xạ vào
không gian (n+1) chiều.
Ví dụ 1.1: điểm P(x, y , z) trong hệ tọa độ Đề-các 3 chiều được biểu diễn
dưới dạng tọa độ đồng nhất 4 chiều P'(x',y',z',h) theo mối quan hệ:
x = x'/h; y = y'/h; z = z'/h (1.4)
trong đó h ≠0 là hệ số vô hướng.
Mối quan hệ (1.4) dựa trên thực tế, nếu tọa độ Đề-các của điểm P được
nhân với hệ số h, điểm P sẽ được di chuyển tới vị trí mới P'(x',y',z') theo phép
lấy tỷ lệ với hệ số h.
Tổng quát, ta có thể biểu diễn phép biến đổi 2D tuyến tính (1.1), (1.2),
(1.3) dưới dạng ma trận bởi vector tọa độ đồng nhất (chuẩn tắc) P
h
, P'
0 0
0
0
0 0 1
; =
0
0
0 0 1
(1.6)
1.1.3. Các phép biến đổi tọa độ 3D
Phép biến đổi tọa độ 3D là mở rộng của phép biến đổi tọa độ 2D. Tọa độ
(x', y', z') của điểm P(x, y, z) sau phép biến đổi tọa độ 3D, tương ứng với
vector dịch chuyển t(t
x
, t
y
, t
z
); hệ số tỷ lệ s(s
x
, s
y
, s
z
) được xác định như sau:
5
h
S (1.10)
trong đó: P
h
= (x y z 1) ;
P'
h
= (x' y' z 1).
=
1 0
0 1
0 0
0 0
0 0
1 0
1
; =
0
0
0 0
0 0
, θ
=
1 0
0 c
0 0
s 0
0 s
0 0
c 0
0 1
; R
y, θ
=
c 0
0 1
s 0
0 0
s 0
0 0
c 0
0 1
; R
z, θ
23
0
31
32
33
0
1
=
0
0
0
1
Với
=
= (r
11
r
12
r
13
);
2
= (r
21
r
22
r
23
);
3
= (r
31
r
2
,
3
=
1
;
3
,
1
=
3
= 1
1.1.4. Phép ánh xạ
Ở các phần trên ta đã xét các phép biến đổi tọa độ trong cùng một hệ tọa
độ mà hoàn toàn không có sự thay đổi hệ tọa độ tham chiếu về vị trí cũng như
phương chiều. Trong phần này ta sẽ xét tới phép ánh xạ đối tượng hình học
giữa 2 hệ tọa độ khác nhau.
7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Phép ánh xạ đối tượng hình học từ một hệ tọa độ sang hệ tọa độ thứ hai
được định nghĩa như sự thay đổi mô tả đối tượng hình học từ hệ tọa độ thứ
nhất sang hệ tọa độ thứ hai. Do đó, không có sự thay đổi về vị trí và phương
chiều của đối tượng hình học so với cả 2 hệ tọa độ.
Phép ánh xạ tương đương với phép biến đổi hệ tọa độ thứ nhất sang hệ
tọa độ thứ hai và được sử dụng rất phổ biến trong thiết kế đồ họa.
Thông thường, người ta sử dụng định nghĩa hệ tọa độ làm việc (còn
được gọi là hệ tọa độ địa phương hay hệ tọa độ đối tượng) gắn liền với đối
tượng thiết kế để đơn giản hoa việc thiết lập và nhập dữ liệu hình học.
Phần mềm thiết kế sẽ ánh xạ (chuyển đổi) tọa độ được đo trong hệ tọa độ
làm việc sang hệ tọa độ hệ thống trước khi lưu trữ trong hệ cơ sở dữ liệu hệ
của hệ tọa độ tham chiếu:
i
h
= (l 0 0 1);
j
h
= (0 1 0 1);
k
h
= (0 0 1 1).
Áp dụng phép biến đổi (1.12) với các vector đồng nhất ta có:
i'
h
= i
h
H = (1 0 0 1) H = (
1
1) (1.17a)
j'
h
= j
h
H = (0 1 0 1)H = (
2
,
3
của ma trận biến đổi
đồng nhất H trở thành vector trục của hệ tọa độ chuyển động (Hình 1.2) biến
đổi theo (1.12). Gốc hệ tọa độ chuyển động được xác định tương tự:
P'
h
= (0 0 0 1) H = (t
x
t
y
t
z
1) = (t 1) (1.18)
Vì lý do này, người ta gọi ma trận biến đổi đồng nhất H là khung tọa độ.
Như vậy, phép biến đổi (1.12) chính là phép ánh xạ từ hệ tọa độ làm việc
(hệ tọa độ địa phương hay hệ tọa độ chuyển động) sang hệ tọa độ hệ thống (hệ
tọa độ cố định). 9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
2
3
H
r
’
j
y
k
và đi qua các điểm điều khiển trung gian theo thứ tự P
0
, P
1
, P
2
, , P
n
. C
kết thúc tại P
n
.
Xấp xỉ các điểm điều khiển: C không nhất thiết phải đi qua các điểm
điều khiển nhưng hình dạng của nó được quyết định bởi các điểm điều
khiển.
Đường cong là các đối tượng cơ bản thường là kết quả của tiến trình
thiết kế và các điểm điều khiển đóng vai trò là công cụ để kiểm soát và mô
hình hoá đường cong. Cách tiếp cận này là cơ sở của lĩnh vực thiết kế mô
hình hình học nhờ máy tính (Computer Aided Geometric Design, viết tắt là
CAGD).
Về mặt toán học, đường cong được biểu diễn dưới các dạng:
Phương trình ẩn:
f(x, y, z) = 0
Phương trình tường minh:
y = f(x), z = g(x)
Phương trình tham số:
x = x(t), y = y(t), z = z(t) trong đó t [0; 1].
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Ví dụ 1.3: Xét đường tròn đơn vị (O, 1) trên mặt phẳng Oxy, có tâm
x = x(t) = (1 - t
2
)(1 + t
2
); y = y(t) = 2t/(1 + t
2
).
Phương trình trên đường gọi là phương trình tham số đa thức hữu tỷ của
đường tròn. Quá trình thiết lập phương trình tham số hữu tỷ của đường cong
và mặt cong từ phương trình đa thức ẩn được gọi là tham số hóa.
θ
0
y
x
P(x,y)
0
y
x
P(x,y)
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Mặc dù về mặt lý thuyết có thể sử dụng phương trình toán học bất kỳ để
biểu diễn đường cong, nhưng mô hình toán học dưới dạng đa thức được sử
dụng phổ biến nhất do có đặc tính dễ dàng xử lý, đủ linh hoạt để mô tả phần
lớn các loại đường cong sử dụng trong kỹ thuật.
Mỗi đường cong có các đặc tính đó là: Độ chảy, Vector tiếp tuyến đơn
vị, Vector pháp tuyến chính, Độ cong và bán kính cong [5].
Xét đường cong được biểu diễn bằng phương trình tham số chuẩn tắc:
r = r(t) = [x(t), y(t), z(t)]
k = |/|
Xét đường tròn trên mặt phẳng mật tiếp đi qua điểm hiện thời r(t) và độ cong
của nó bằng chính độ cong của đường cong tại điểm này. Đường tròn này
được gọi là đường tròn mật tiếp, bán kính của đường tròn mật tiếp được gọi là
bán kính cong và được xác định bởi:
=
1
1.3. Mặt cong - Surface
1.3.1. Biểu diễn mặt cong
Mặt cong được định nghĩa trực quan là quỹ đạo chuyển động của một
đường cong tạo nên.
Theo hình học vi phân, mặt cong được định nghĩa như là ảnh của phép
ánh xạ tập hợp điểm trong không gian 2D vào không gian 3D và được biểu
diễn bởi phương trình:
x = x(u, v) với u, v [0, 1]
y = y(u, v)
z = z(u, v)
S(u,v,w) = S[x = x(u,v), y=y(u,v), z=z(u,v)] (1.19)
Trong đó u, v, w là tham số của mặt cong.
Để biểu diễn phương trình tham biến cho mặt cong ta có thể:
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Dựa vào việc xây dựng và tạo bề mặt toán học từ các điểm dữ liệu
điều khiển
Dựa vào việc xây dựng nên bề mặt phụ thuộc vào biến số có khả năng
thay đổi một cách trực diện thông qua các tương tác đồ hoạ.
Ta cũng có thể biểu diễn theo mảnh tam giác (Triangular Patches) hoặc
tứ giác (Quadrilatera Patches).
=
1
1
+
2
= [
1
]
1
()
2
()
(1.20)
b. Mặt tròn xoay - Revolution surface
Hình 1.5 Mô hình mặt tròn xoay
Mặt tròn xoay được xây dựng bởi đường thẳng hay một đường cong
Lấy một mẫu đường cong chừng vài chục điểm cách nhau tương đối
ngắn rồi tìm một hàm toán học và chỉnh hàm này sao cho nó đi qua các
điểm này và khớp với đường cong ban đầu. Khi đó, ta có được công
thức của đường và dùng nó để vẽ lại đường cong.
Dùng một tập các điểm kiểm soát và dùng một thuật toán để xây dựng
nên một đường cong của riêng nó dựa trên các điểm này. Có thể đường
cong ban đầu và đường cong tạo ra không khớp nhau lắm, khi đó ta có
thể di chuyển một vài điểm kiểm soát và lúc này thuật toán lại phát sinh
một đường cong mới dựa trên tập điểm kiểm soát mới. Tiến trình này
lặp lại cho đến khi đường cong tạo ra khớp với đường cong ban đầu.
Ở đây, ta sẽ tiếp cận vấn đề theo phương pháp thứ hai tức là sử dụng các
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
điểm kiểm soát để xây dựng đường cong. Giả sử một điểm trong không gian
được biểu diễn dưới dạng vector tham số p(t). Với các đường cong 2D, C(t) =
(x(t), y(t)) và các đường 3D, C(t) = (x(t), y(t), z(t)).
Để xây dựng đường cong C(t), ta dựa trên một dãy các điểm cho trước
rồi tạo ra giá trị C(t) ứng với mỗi giá trị t nào đó. Việc thay đổi các điểm này
sẽ làm thay đổi dạng của đường cong. Phương pháp này tạo ra đường cong
dựa trên một dãy các bước nội suy tuyến tính hay nội suy khoảng giữa (In-
Betweening).
* Thuật toán Casteljau: Thuật toán này dựa trên tập các điểm cho trước
để tìm ra các giá trị p(t) khi t thay đổi. Lúc này do đường cong được xây dựng
phụ thuộc vào tập các điểm cho trước nên khi thay đổi các điểm này đường
cong sẽ thay đổi theo. Với 3 điểm cho trước P
0
, P
1
, P
2
0
+ tP
1
(2.1)
P
1
1
(t) = (1 – t)P
1
+ tP
2
(2.2)
P
1
P
1
1
(t)
P
2
P
0
1
(t)
P
0
P
0
2
= (1 – t)((1 – t)P
0
+ tP
1
) + t((1 – t)P
1
+ tP
2
) =
= (1 – t)
2
P
0
+ 2t(1 – t)P
1
+ t
2
P
2
. (2.3)
Công thức (2.3) là hàm bậc 2 theo tham số t do vậy tập các điểm P
0
2
(t)
sẽ tạo thành đường cong Parabol.
* Thuật toán Casteljau cho (n+l) điểm:
Xét tập điểm: P
0
, P
1
, P
1
, P
2
, …, P
n
. Các điểm P
i
, i = 0, l, , n
được gọi là các điểm kiếm soát (điểm điều khiển) hay các điểm Bezier. Đa
giác tạo bởi các điểm kiểm soát này gọi là đa giác kiếm soát (đa giác điều
khiển) hay đa giác Bezier.
2.2. Đƣờng cong và mặt cong Bezier
Lí thuyết đường cong và mặt Bezier được phát minh bởi một kĩ sư người
Pháp có tên là Pierre Bezier trong quá trình thiết kế mẫu xe ôtô. Bezier là
nhân viên hãng RENAULT. Vào những năm 1970 ông là người đi đầu trong
việc ứng dụng máy tính cho việc xây dựng các bề mặt. Hệ thống UNISURF
Copyright: Tài liệu đại học ©