Bài giảng Công nghệ đồ họa và hiện thực ảo - Bài 8: Đường cong - Trịnh Thành Trung

©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
Trịnh Thành Trung 
trungtt@soict.hust.edu.vn 
Bài 8 
ĐƯỜNG CONG 
1 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
NỘI DUNG 
1. Các khái niệm 
2. Phân loại 
3. Đường cong đa thức bậc 3 
4. Đường cong Spline 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
KHÁI NIỆM 
1 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 4 
• Đường cong – Curve: 
– Quỹ đạo chuyển động của 1 điểm trong 
không gian 
Đường cong 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 5 
• Điểm biểu diễn đường cong - curve represents 
points: 
– Là phương pháp được sử dụng trong khoa 
học vật lý và kỹ nghệ nói chung. 
– Các điểm dữ liệu được đo chính xác trên các 
thực thể sẽ chính đối tượng cơ sở. Đường 
cong đi qua các điểm dữ liệu hiển thị hỗ trợ 
cho việc nhận ra xu hướng và ý nghĩa cả các 
điểm dữ liệu. 
– Các kỹ thuật phức tạp (VD: bình phương sai 
số) được dùng đưa đường cong hợp với 1 
dạng toán học cơ bản. 
Điểm biểu diễn đường cong 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 6 
Điểm biểu diễn đường cong 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 7 
• Biểu diễn điểm và kiểm soát đường cong - 
Points represent and control curve. 
– Đườ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 
đóng vai trò là công cụ để kiểm soát và và mô 
hình hoá đường cong. 
– Là cơ sở của lĩnh vực Computer Aided 
Geometric Design (CAGD). 
Biểu diễn điểm và 
kiểm soát đường cong 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 8 
Biểu diễn điểm và 
kiểm soát đường cong 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
PHÂN LOẠI 
2 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 10 
• Nội suy- Interpolation: đường cong đi qua các 
điểm, trong ứng dụng khoa học các yêu cầu về 
ràng buộc sử dụng đa thức hay các hàm bậc cao 
tuy nhiên kết quả thường có những hiệu ứng phụ 
như sai số phóng đại hay độ nhấp nhô của 
đường cong do đa thức bậc cao tạo nên. 
Nội suy 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 11 
– Trong thiết kế nôi suy là cần thiết với các đối 
tượng nhưng không phù hợp với các đối 
tượng có hình dáng bất kỳ "free form“. 
Nội suy 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 12 
• Xấp xỉ - Approximation: đường cong không cần 
đi qua các điểm,với các ứng dụng khoa học ta 
gọi là trung bình dữ liệu- data averaging hay 
trong thiết kế điểu khiển đường cong. 
Xấp xỉ 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
NỘI SUY VS. XẤP XỈ 
13 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
ĐƯỜNG CONG BẬC 3 
3 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 15 
• Là đường cong không gian với 3 trục toạ độ x, y, 
z 
• Tránh được những tính toán phức tạp và những 
phần nhấp nhô ngoài ý muốn xuất hiện ở những 
đường đa thức bậc cao 
Đường cong đa thức bậc ba 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 16 
• Tham biến – parametric sử dụng tham biến ngoài để biểu 
diễn cho các tham biến trong 
• Độ mượt - smooth. Với đường cong Hermite and Bézier 
tính liên tục continuity của đường cong hay đạo hàm bậc 
1-first derivative tại các điểm kiểm soát-control point. 
Với B-splines tính liên tục trên đạo hàm bậc 2 second 
derivative hay độ cong được đảm bảo curvature. 
• Độ biến đổi - variation diminishing. đường cong ít bị 
khuếch đại sai số bởi các điểm kiểm soát hay tính nhấp 
nhô của đường cong hạn chế -oscillate. 
• Điểm kiểm soát cục bộ-local control. đường cong bị ảnh 
hưởng mạnh nhất với chính các điểm kiểm soát gần 
chúng nhất. 
Tính chất 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 17 
• Theo LeGrange: 
– x = a1 + b1u + c1u
2 + d1u
3 
– y = a2 + b2u + c2u
2 + d2u
3 
– z = a3 + b3u + c3u
2 + d3u
3 
• 3 phương trình với 12 ẩn số 
• Với 4 điểm P0, P1, P2, P3 phương trình xác định 
Đường cong LeGrange 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 18 
• Phương pháp Hermite dựa trên cơ sở của cách biểu diễn 
Ferguson hay Coons năm 60 
• Đường bậc ba sẽ xác định bởi hai điểm đầu và cuối cùng với 
hai góc nghiêng tại hai điểm đó 
– p = p(u) = k0 + k1u + k2u
2 + k3u
3 
– p(u) = kiu
i i n 
– p’ = p’(u) = k1 + 2k2u + 3k3u
2 
• p0 và p1 ta có hai độ dốc p0’ và p1’ với u = 0 và u = 1 tại hai 
điểm đầu cuối của đoạn [0,1]. 
– k1 + 2k2 + 3k3 = p1’ 
– k0 = p0 k1 = p1’ 
– k2 = 3(p1 – p0) - 2p0’ – p1’ 
– k3 = 2(p0-p1) + p0’ + p1’ 
Đường cong Hermite 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
Thay vào: 
• p = p(u) = p0(1-3u
2+2u3) + p1(3u
2-2u3) 
 + p0’(u-2u
2+u3) + p1’(-u
2+u3) 
 19 
p = p(u) = [ 1 u u2 u3 ] 
1
0
1
0
'
'
.
1122
1233
0100
0001
p
p
p
p
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
VÍ DỤ ĐƯỜNG CONG HERMITE 
 20 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 21 
• Sử dụng điểm và các vector kiểm soát được độ 
dốc của đường cong tại nhưng điểm mà nó đi 
qua 
• Không được thuận lợi cho việc thiết kế tương 
tác, không tiếp cận vào các độ dốc của đường 
cong bằng các giá trị số 
Nhược điểm của Hermite 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
22 
• Paul Bezier, RENAULT, 1970, Đường và bề mặt 
UNISURF 
• Là biến thể của đường cong Hermite 
• Mỗi đường cong được điều khiển bởi 4 điểm 
Đường cong Bezier 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 23 
• po, p3 tương đương với p0, p1 trên đường Hermite. 
diểm trung gian p1, p2 được xác định bằng 1/3 theo 
độ dài của vector tiếp tuyến tại điểm po và p3 
• p0’ = 3(p1 – p0) 
• p3’ = 3(p3 – p2) 
• p = p(u) = p0(1-3u
2+2u3) + p1(3u
2-2u3) + p0’(u-
2u2+u3) + p1’(-u
2 + u3) 
• p = p(u) = p0(1 - 3u + 3u
2 - u3) + p1(3u-6u
2+3u3) 
+ p2(3u
2 - 3u3) + p3u
3 
Đường cong Bezier 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 24 
p = p(u) = [ 1 u u2 u3 ] 
3
2
1
0
1331
0363
0033
0001
p
p
p
p
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 25 
• Dễ dàng kiểm soát hình dạng của đường cong 
hơn vector tiếp tuyến tại p0’ và p1’ của Hermite. 
• Nằm trong đa giác kiểm soát với số điểm trung 
gian tuỳ ý (số bậc tuỳ ý) 
• Đi qua điểm đầu và điểm cuối của đa giác kiểm 
soát, tiếp xúc với cặp hai vector của đầu cuối đó 
Ưu điểm 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 26 
• Tổng quát hoá với n +1 điểm kiểm soát 
• p0 ... pn : vector vị trí của đa giác n+1 đỉnh 
Biểu thức Bezier-Bernstain 
))(()(
)()(
1
0
1,
0
,
ii
n
i
ni
i
n
i
ni
PpuBnup
puBup


ini
ni uuinCuB
 )1(),()(,
)!in(!i
!n
)i,n(C
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 27 
• P0 và Pn nằm trên đường cong. 
• Đường cong liên tục và có đạo hàm liên tục tất 
cả các bậc 
• Tiếp tuyến của đường cong tại điểm P0 là đường 
P0P1 và tại Pn là đường Pn-1Pn . 
• Đường cong nằm trong đường bao lồi convex 
hull của các điểm kiểm soát. 
• P1, P2, ,Pn-1 nằm trên đường cong khi và chỉ khi 
đường cong là đoạn thẳng. 
Tính chất 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
ĐƯỜNG CONG SPLINE 
4 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 29 
• Spline đi qua n điểm cho trước mà mỗi đoạn là 
đường bậc ba độc lập có độ dốc và độ cong liên tục 
tại mỗi điểm kiểm soát hay điểm nút 
• Với n điểm:n-1 đoạn với mỗi đoạn 4 vector hệ số 
4(n-1) cho n-1 đoạn, và 2(n-1) điều kiện biên và n-
2 điều kiện về độ dốc cùng n-2 về độ cong 
• Spline dùng để chỉ phương pháp biểu diễn đường 
cong mềm thông qua các đoạn cong tham biến bậc 
ba với các điều kiện liên tục tại các điểm đầu nút 
Đường bậc ba Spline 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
30 
• u0 = 0 với : (u0 ... un-1) uj+1 > uj 
• ui+1 = ui + di+1 
• C0 để không có sự gián đoạn giữa hai đoạn 
cong. 
• C1 tính liên tục bậc nhất hay đạo hàm bậc nhất 
tại điểm nối. 
• C2 đạo hàm bậc hai liên tục của đường cong 
tại điểm nối 
Đường bậc ba Spline 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
31 
• Tính liên tục của đạo hàm bậc hai tại các điểm nối có 
thể dễ dàng đạt được bằng cách đặt P’’i-1(ui-1=1) là 
đạo hàm bậc hai tại điểm cuối của đoạn (i-1) bằng với 
P’’i(ui=0) đạo hàm bậc hai tại điểm đầu của đoạn thứ i. 
• P’’i-1(1)= P’’i(0) 
y Pn-1
’ 
 Pn-1 
 Po
’ P1 
x z Po 
p = [ 1 u u2 u3 ] 
1
0
1
0
1122
1233
0100
0001
'
'
.
p
p
p
p
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 32 
• Đường cong B-spline là đường cong được sinh 
ra từ đa giác kiểm soát mà bậc của nó không 
phụ thuộc vào số đỉnh của đa giác kiểm soát. 
Đường cong B-spline 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 33 
• Ni,k(u) đa thức B-Spline cơ bản 
• Với n+1 số điểm kiểm soát 
• Pi điểm kiểm soát thứ i 
• k bậc của đường cong 1<k<n+2 
• Ui vector nút của đường cong U=[U1,U2...Un+k+1] 
B-spline 
i
n
i
ki PuNuP 
0
, ).()(
)(
)(
)(
)(
)(
)( 1,
21
1
1,1
1
1
, uN
UU
uU
uN
UU
Uu
uN ki
kii
i
ki
kii
ki
ki 
others0
],[1
)(
1
1,
ii
i
uuu
uN
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 34 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 35 
• B-spline không đi qua hai điểm đầu và cuối trừ khi hàm hợp 
được dùng là tuyến tính. 
• B-spline có thể được tạo qua hai điểm đầu, cuối và tiếp xúc 
với vector đầu và cuối của đa giác kiểm soát. Bằng cách thêm 
vào các nút tại vị trí của các nút cuối của vector tuy nhiên các 
giá trị giống nhau không nhiều hơn bậc của đường cong. 
• Tính chất bao lồi của đa giác kiểm soát và tính chất chuẩn 
được thỏa mãn. 
• Số lượng các nút, bậc của đường cong và số điểm điều khiển 
luôn có các quan hệ ràng buộc: 
 0 u n - k + 2 
Đặc điểm 
1(u)N
n
0i
ki, 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 36 
• Vecto nút là đều khi giá trị của chúng cách đều nhau một 
khoảng  xác định. Trong các bài toán thực tế, vecto nút 
đều được bắt đầu từ 0 và tăng 1 cho đến giá trị lớn nhất 
– Ví dụ: [ 0 1 2 3 4 5 ] với  xác định = 1 
– [ -2 -1/2 1 5/2 4 ] với  xác định = 3/2 
• Với cấp là k, số điểm kiểm soát là n+1 thì vecto nút đều là 
– U=[0 1 2 ...n+k] khoảng tham số (k-1)≤u≤(n+1). 
• Khi vecto nút là đều thì ta có Ni,k(u)=Ni-1,k(u-
1)=Ni+1,k(u+1) 
B-spline đều và tuần hoàn 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
- 
VÍ DỤ 
 37 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
• Một vector không tuần hoàn hoặc mở (open – non 
uniform) là vector nút có giá trị nút tại các điểm đầu cuối 
lặp lại với số lượng các giá trị lặp lại này bằng chính cấp k 
của đường cong và các giá trị nút trong mỗi điểm lặp này 
là bằng nhau 
• Nếu một trong hai điều kiện này hoặc cả hai điều kiện 
không được thoả mãn thì vecto nút là không đều. 
• Cách tính Ui 
– Ui = 0 1=<i<=k 
– Ui = i-k k+1<i<=n+1 
– Ui = n-k+2 n+1<i<=n+k+1 
Không tuần hoàn 
2 
6 
[0 0 1 2 3 3] 
3 
7 
[0 0 0 1 2 2 2] 
4 
8 
[0 0 0 0 1 1 1 1] 
Cấ
p k 
số lượng nút 
(m = n + k) 
Vector nút 
không tuần 
hoàn 
©
 C
o
p
yrigh
t Sh
o
w
eet.co
m
 39 
• B-spline là một dòng của Bezier 
– Thực tế khi ta chọn bậc k cho tập hợp k điểm thì thi B-spline 
chuyển thành Bezier 
• Khi bậc của đa thức giảm sự ảnh hưởng cục bộ của mỗi điểm nút 
càng rõ ràng hơn. 
• Khi tồn tại anh hưởng cục bộ càng lớn và đường cong phai đi 
qua điểm đó. 
• Chúng ta có thể thay đổi hình dạng đường cong B-spline bằng 
cách: 
– Thay đổi kiểu vecto nút: đều tuần hoàn, mở, không đều 
– Thay đổi cấp k của đường cong 
– Thay đổi số đỉnh và vị trí các đỉnh đa giác kiểm soát 
– Sử dụng các điểm kiểm soát trùng nhau 
B-spline