1

MỞ ĐẦU
1. Lý do chọn đề tài
Công nghệ thông tin ngày càng phát triển và đồ họa máy tính là một
lĩnh vực công nghệ phát triển rất nhanh. Đồ họa đã được áp dụng rộng rãi
trong 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 và xây dựng một ứng dụng trong bài
toán thiết kế hình học. Đây là việc làm có ý nghĩa khoa học và thực tiễn.
2. Đối tượng nghiên cứu
Cơ sở mô hình hóa hình học, Phương pháp sinh đường cong và mặt
cong nhờ các điểm điều khiển, B - splines, Ứng dụng B- splines trong đồ
họa
3. Phạm vi nghiên cứu
Đề tài tập trung tìm hiểu lý thuyết về splines, B-splines và ứng dụng.
4. Nhiệm vụ nghiên cứu
 Tìm hiểu các kiến thức cơ sở về hình học đường cong và mặt cong, các
phép biến đổi tọa độ trong không gian 2D và 3D.
 Tìm hiểu lý thuyết về splines, B-splines sinh đường cong và mặt cong


2

1.1. Cơ sở của mô hình hóa hình học
1. 1. 1. Các phép biến đổi hình học trong không gian 2D và 3D
Tất cả các phép biến hình trong ĐHMT và mô hình hóa hình học đều
dựa trên 3 hình thức biến đổi tọa độ cơ bản là dịch chuyển tịnh tiến, lấy tỷ
lệ và quay [3].
Xét điểm P'(x', y') là vị trí của điểm P(x, y) sau phép biến đổi tọa độ. Tọa
độ (x', y') của điểm P' tương ứng với vector dịch chuyển t(tx, ty) (Hình 1.1a),
hệ số tỷ lệ s(sx, sy) (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 + tx;

y' = y + ty

(1.1)

x' = sxx;

y' = syy

(1.2)

x' = xcosθ – ysinθ;

y' = xsinθ + ycosθ

(1.3)

y

y


x

o

b

r
x

α
c

Hình 1.1: Phép biến đổi tọa độ 2D
Phép biến đổi tọa độ 3D là mở rộng của phép biến đổi tọa độ 2D. Tọa độ


4

(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(tx, ty, tz); hệ số tỷ lệ s(sx, sy, sz) được xác định như
sau:
x' = x + tx;

y' = y + ty;

z' = z + tz

(1.4)


0 s

1 0 0
y
S
;
0 0
0 1 0


t y t z 1 
0 0

z 1).
0 0
0 0 
sz 0 

0 1

Đối với phép quay 3D, việc xác định phép quay quanh trục bất kỳ trong
không gian là rất khó, do vậy phép quay quanh trục bất kỳ thường được qui
về các phép quay cơ bản quanh các trục hệ tọa độ như trong Bảng 1.1:
X'

Y'

Z'

x' = x

5

1 0 0 0 
0 c s 0

R ( x,  )  
0 s c 0


0 0 0 1

c
0
R( y, )  
s

0

0 s 0
1 0 0 
0 c 0

0 0 1

 c s 0 0
s c 0 0

R( z,  )  
 0 0 1 0


ty

tz

r12
r22
r32

r13 
r23 
r33 

0 
0  

0 
 
1  

R*
t

0
0 
0

1

với


ur ur
ur
 r1 , r2   r3



ur ur
ur
 r2 , r3   r1



ur ur
ur
 r3 , r1   r2



(1.12)

và ta còn có :

ur ur ur
r1  r2  r3  1
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.

T  0 1
t x t y


 sx
S   0
 0

0

0 ;
1 

0
sy
0

0
0  ;
1 

 cos 
R    sin 
 0

sin 
cos 
0

0


ur ur ur
Kết quả trên đây cho thấy rằng các vector r1 , r2 , r3

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 = (tx ty tz 1) = (t

1)

(1.17)

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


8

ur
r1
r
H

P

ur

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 hóa việc thiết lập và nhập dữ liệu hình học.


9

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ệ thống.
Phép ánh xạ đóng vai trò quan trọng đối với cấu trúc lắp ghép, khi mỗi
đối tượng (chi tiết hay bộ phận) được định nghĩa theo hệ tọa độ hệ thống
riêng và chúng cần được kết nối và quản lý trong hệ tọa độ hệ thống chủ.
Ví dụ 1.1: Ta có thể đặt bài toán ánh xạ điểm từ một hệ tọa độ sang
hệ tọa độ thứ hai như sau: Cho trước tọa độ của điểm P xác định theo hệ tọa
độ (X, Y, Z), ta sẽ xác định tọa độ của điểm P theo hệ tọa độ (X', Y', Z'), sao
cho thỏa mãn điều kiện:
P' = f(P, thông số ánh xạ) hay P' = P.H
trong đó:
P: Vector vị trí của điểm P theo hệ tọa độ (X, Y, Z).
P': Vector vị trí của điểm P theo hệ tọa độ (X', Y', Z')
H : Ma trận ánh xạ trong công thức (1.9) mô tả vị trí tương đối của
hệ tọa độ (X, Y, Z) so với hệ tọa độ (X', Y', Z').
1.2. Đường cong
Trong các ứng dụng của ĐHMT, hầu như các thực thể là đường cong và
mặt cong. Các thực thể này được dùng để mô tả các vật thể trong thế giới
thực như nhà cửa, đồi núi, phương tiện đi lại…hay để xây dựng các thực thể
đang được thiết kế. Nếu chỉ sử dụng các phương trình đường cong sẽ
không thể hiện được hình ảnh thực hay ý tưởng của người thiết kế, ngược lại
nếu dùng tập hợp các điểm thì thường cần phải dùng nhiều dung lượng nhớ

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)


11

 Phương trình tham số:
x = x(t), y = y(t), z = z(t) trong đó t

[0; 1].

Ví dụ 1.2: Xét đường tròn đơn vị (O, 1) trên mặt phẳng Oxy, có
tâm trùng với gốc hệ toa độ như trên (Hình 1.3). Mối quan hệ giữa các tọa độ
x và y được mô tả bởi phương trình ẩn:
f ( x , y ) = x 2 + y 2 - 1 =0
Nếu ta chỉ xét phần nửa trên của đường tròn thì ta có phương trình
tường minh biểu diễn là:
y = g(x) = (1 – x2)1/2
y

y
P(x,y)

P(x,y)

θ
0

và mặt cong từ phương trình đa thức ẩn được gọi là tham số hóa.
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 [3].
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)]
Độ chảy : Độ lớn của vector đạo hàm r’(t) được gọi là độ chảy của
đường cong :
q’(t) = r '( t )
Nếu so sánh đường cong là con đường và t là tham số tượng trưng cho
thời gian thì khi đó độ chảy của đường cong tương ứng với tốc độ chạy xe.
Đại lượng này được sử dụng trong thuật toán nội suy hình học theo phương
pháp quét hình. Nếu đặt quãng đường đi được là tham số s, phương trình
đường cong dạng r(s) trở thành phương trình tham số tự nhiên với độ chảy
bằng 1. Độ chảy của đường cong không phải là đặc tính riêng của đường
cong đó, mà đó là kết quả của phép tham số hóa.
Vector tiếp tuyến đơn vị: Cho s là tham số tự nhiên của đường cong
r(t), sao cho:


s 



r '( t ) d t

0

1.3. Mặt cong
1.3. 1. Mô hình hóa mặt cong
Mô hình hóa các mặt cong ta có thể xây dựng được bằng ba cách sau:
a. Mặt kẻ - Ruled Surface
Mặt kẻ được xây dựng bằng cách cho trượt một đoạn thẳng trên hai
đường cong. Hai đường cong này gọi là đường cong biên. Các mặt kẻ nhận
được bằng phép nội suy tuyến tính từ hai đường cong biên cho trước tương
ứng với hai biên đối diện của mặt kẻ P1(u) và P2(u).


14

Hình 1.4: Mô hình bề mặt kẻ
ta có phương trình mặt kẻ:
S(u,v) = P2(u)v + P1(u)(1-v)
nếu hai đường cong cho trước tương ứng là P1(v) và P2(v)
thì mặt kẻ có phương trình:
 P (v ) 
Q(u , v)  P1 (v)(1  u )  P2 (v)u  [(1-u)]  1 
 P2 (v) 

(1.18)

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
phẳng, quanh một trục trong không gian.
c. Mặt trượt - Sweept Surface


16

khả năng thay đổi một cách trực diện thông qua các tương tác
đồ họa.
Ta cũng có thể dùng mảnh tam giác (Triangular Patches ) hoặc tứ giác
(Quadrilatera Patches) để biểu diễn.
Kết chương:
Ở chương này trình bày một số kiến thức cơ bản đường cong và mặt
cong. Qua đó có cái nhìn và tư duy cơ bản về các dạng đường cong và mặt
cong, giúp em định hướng rõ hơn về hướng nghiên cứu chính của mình sẽ
được trình bày trong chương tiếp theo.


17

CHƯƠNG 2. B-SPLINE TRONG KHÔNG GIAN 2D VÀ 3D
Chương này trình bày về một số đường cong và mặt cong, trong đó chủ
yếu là tìm hiểu về đường cong và mặt cong B-spline.
2.1. Sơ lược về đường cong và mặt cong Bezier
Lý thuyết đường cong và mặt cong 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 của ông được áp dụng trong thực tế vào năm 1972 được thiết kế
và kiểm tra xe Mezesez hay Renault. Điểm mạnh của lý thuyết Bezier là tính
dễ dàng và thuận tiện trong việc biểu diễn các đường cong và mặt cong.
Bezier đã sử dụng đa giác kiểm soát cho đường cong tại những đỉnh của đa
giác và tiếp tuyến tại đó.
2.1.1. Đường cong Bezier
Giả sử một đường cong Bezier C được tạo ra từ (n+1) điểm điều khiển P0,

C(t) = B0,1.P0 + B1,1.P1 = (1 - t)P0 + tP1, (0 ≤ t ≤ 1)

(2.2)

đường cong C đi qua 2 điểm P0 và P1 lúc này chính là đoạn thẳng P0P1
như trong (hình 2.1a). Ta thấy C(t) là tuyến tính theo tham số t và ta gọi đó là
đường cong Bezier bậc 1.
Trường hợp có 3 điểm điều khiển P0, P1, P2 như trong (Hình 2.1b), ta có :
B0,2 = (1 - t)2
B1,2 = 2t(1 - t)
B2,2 = t2
khi đó phương trình của đường cong C là :
C(t) = (1 - t)2P0 + 2t(1 - t)P1 + t2P2
P1

(2.3)

P1

P2
b(t)
P1

C(t
a(t)
P0

P0
a


C(t) = (1 - t)a(t) + tb(t) = (1 - t)2P0 + 2t(1 - t)P1 + t2P2


19

Tương tự như trên, trong trường hợp có 4 điểm điều khiển P0, P1, P2, P3
như trong (Hình 2.2c), ta tính được :
B0,3 = (1 - t)3
B1,3 = 3t(1 - t)2
B2,3 = 3t2(1 - t)
B3,3 = t3
khi đó phương trình đường cong Bezier đi qua 4 điểm này là :
C(t) = (1 - t)3P0 + 3t(1- t)2P1 + 3t2(1 - t)P2 + t3P3

(2.4)

trong công thức (2.4), C(t) là một hàm bậc 3 theo biến t và được gọi là
đường cong Bezier bậc 3. Công thức này cũng có thể xây dựng một cách tuần
tự bằng thuật toán Casteljau cho 4 điểm.


Dạng biểu diễn ma trận của đường cong Bezier

Để thích hợp cho việc biểu diễn trên máy tính, ta biểu diễn 2 mảng
Bn(t) và P như sau :
Bn(t) = (B0,n(t) , B1,n(t),…,Bn,n(t))
P = (P0, P1, P2,…, Pn)

 P0 
P 

(2.8)

đối với đường cong Bezier bậc 3 ta có ma trận BE3 là :

1 0 0
 3 3 0
BE3  
 3 6 3

 1 3 3


0
0 
0

1

(2.9)

Vẽ đường cong Bezier

Để tạo ra một đường cong Bezier từ một dãy các điểm điều khiển ta sẽ
áp dụng phương pháp lấy mẫu hàm C(t) ở các giá trị cách đều nhau của tham
số t, chẳng hạn có thể lấy ti = i/n, i = 0, 1, …, n. Khi đó ta sẽ được các điểm
C(ti) từ công thức Bezier.
Nối các điểm này bằng các đoạn thẳng ta sẽ được đường cong Bezier
gần đúng. Để tính C(ti) ta có thể áp dụng ma trận C(t) ở công thức (2.8) trong
đó chỉ có thành phần Pow(ti) là thay đổi, còn tích Ben.PT với P = (P0, P1, P2,…,
Pn) là không đổi [3].

với 2 tham số là u, v. Dạng tổng quát của một mặt cong là [4] :
S(u, v) = (X(u, v), Y(u, v), Z(u, v))
< = > S(u, v) = X(u, v).i + Y(u, v).j + Z(u, v).k

(2.10)

khi u, v biến thiên trên một khoảng nào đó thì các hàm X(u, v), Y(u, v)
và Z(u, v) thay đổi giá trị, dó đó làm cho vị trí của S(u, v) thay đổi trong
không gian 3 chiều.
Ở đây, ta sẽ không biểu diễn các mặt cong bằng các hàm toán học
tường minh mà sẽ biểu diễn chúng thông qua các điểm điều khiển. Chẳng
hạn :
S(u, v) = (1 - v).((1 - u).P00 + u.P10) + v.((1 - u).P01 + u.P11) dùng 4 điểm
điều khiển ở 4 góc là Pij với các hàm trộn là tuyến tính theo u, v.
Đường cong Bezier trong không gian 3 chiểu có thể được viết dưới
dạng là một hàm của tham số v với K+1 điểm điều khiển tùy thuộc vào tham
số u theo một cách nào đó. Chẳng hạn :


22
K

C (u, v )   Pi (u ) Bi ,n (v)

(2.11)

i 0

nghĩa là mỗi đường viền u là một đường cong Bezier chuẩn, nhưng ở
những giá trị u khác nhau thì các điểm điều khiển cũng nằm ở những vị trí

một đường cong Bezier. Có thể tưởng tượng rằng khi v tăng từ 0 đến 1 ta sẽ


23

thu được một lưới các đường cong Bezier, đó chính là mặt cong Bezier như
minh họa trong (Hình 2.2).
P30

C3(v)

C2(v)

P20

C3

P32
P31

P33
P21

P22

C2

C1(v)

P10

là cơ sở cho Spline, nghĩa là bất kỳ đường cong spline nào cũng có thể được
đưa về cùng một công thức bằng cách chọn kiểu đa giác kiểm soát phù hợp.
Với mỗi vector có nhiều họ hàm như vậy, nhưng đặc biệt có một họ hàm
trộn có đoạn mang giá trị khác 0 nhỏ nhất đó là Basic Spline (Được viết tắt là
B-spline). Đối với các hàm B-spline, mỗi đa thức riêng phần tạo ra nó có một
bậc m nào đó. Do đó, thay vì dùng ký hiệu Ri(t) như trong phương trình
n

đường cong spline: C (t )   PR
cho các hàm từng mẩu này ta sẽ ký
i i (t )
i0


24

hiệu các hàm trộn này là Nk,m(t). Khi đó, một đường cong B-spline bậc m-1
được xây dựng dựa trên vector nút T và (n+1) điểm điều khiển Pi có dạng:
n

C (t )   PP
i i , m (t )

(2.13)

i 0

trong đó:
Ni,m(t) gọi là hàm Cox-de Boor hay hàm cơ sở B-spline có cấp m (order
m) và bậc (m-1) (degree m-1) là phương pháp chuẩn để định nghĩa hàm cơ

ti 1  ti
ti  2  ti 1

(2.15)


25

 t  ti
  ,
i

t  t
  i2 ,
  i 1
 0,



Với ti ≤ t ≤ ti+1

Với ti+1 ≤ t ≤ ti+2

(2.16)

Với các giá trị t khác

Ta có hình biểu diễn đường cong B-spline như trong (hình 2.3):

Hình 2.3: Đường cong B-spline