Đồ họa 2D - Đường cong

=
8,0t
tsintty
tcosttx
ĐƯỜNG CONG BEZIER
Định nghĩa đường cong
Input
n +1 điểm điều khiển {p0, p1, ... , pn}
Output
p1
Trang 25
p0
pn
Đường cong Bezier bậc một
p(t) = (1 – t)p0 + tp1
t ∈ [0, 1]
hoặc
p1
Trang 26
x(t) = (1 – t)p0x + tp1x
y(t) = (1 – t)p0y + tp1y
t ∈ [0, 1]
p0
Đường cong Bezier bậc hai
p(t) = (1 – t)2p0 + 2(1 – t)tp1 + t2p2
t ∈ [0, 1]
hoặc
p2
p1
Trang 27
x(t) = (1 – t)2p0x + 2(1 – t)tp1x + t2p2x
y(t) = (1 – t)2p0y + 2(1 – t)tp1y + t2p2y
t ∈ [0, 1]
p0
Đường cong Bezier bậc ba
p(t) = (1 – t)3p + 3(1 – t)2tp + 3(1 – t)t2p + t3p
p0
p1
p3
p2
Trang 28
0 1 2 3
t ∈ [0, 1]
hoặc
x(t) = (1 – t)3p0x + 3(1 – t)2tp1x + 3(1 – t)t2p2x + t3p3x
y(t) = (1 – t)3p0y + 3(1 – t)2tp1y + 3(1 – t)t2p2y + t3p3y
t ∈ [0, 1]
Một số đường cong Bezier bậc ba
Trang 29
Công thức xác định đường cong
( ) ( )
[ ]
( ) ( )
hoặc
t)t1(
!kn!k
!n
tB với
1,0t
p.tBtp
khiển điều điểm 1n bởi tạo được n bậc Bezier cong đường Ptts
nk
kknn
k
nk
0k
k
n
k
−
−
=
∈
=
+
∑
=
−
=
=
Trang 30
( ) ( )
( ) ( )
[ ]1,0t
p.tBty
p.tBtx
nk
0k
ky
n
k
0k
xk
n
k
∈
=
=
∑
∑
=
=
=
Tính chất 1
Bảo toàn qua phép biến đổi affine.
Trang 31
Tính chất 2
Các điểm điểu khiển tạo thành bao lồi của đường cong
Trang 32
Độ thẳng của đường cong Bezier
p0
p1 p2
p3
Trang 33
30
322110
pp
pppppp
f
−
−+−+−
=
Thuật toán vẽ đường cong Bezier
Trang 34
Thuật toán vẽ đường cong Bezier

Xét đường cong Bezier với các điểm điều khiển {p0, p1, 
... , pn}, nối các điểm liên tiếp để tạo thành đa giác điều 
khiển

Chia mỗi đoạn trong đa giác với tỉ số t:(1-t), nối các 
điểm mới tính, ta có được đa giác với số đỉnh ít hơn 1

Lặp lại bước trên cho đến khi chỉ còn một điểm đơn, 
chính là điểm của đường cong Bezier ứng với tham số t
Trang 35
Đạo hàm
p’(0) = 3(p1 – p0)
p’(1) = 3(p3 – p2)
p”(0) = 6(p0 – 2p1 + p2)
p”(1) = 6(p1 – 2p2 + p3)
pp
Trang 36
p0
p3
21
Tính liên tục
•Một đường cong Bezier không đủ phức tạp
•Ghép nhiều đường cong Bezier với nhau
•Yêu cầu tính liên tục tại các điểm ghép nối
•Liên tục tham số
C0: liên tục tham số bậc 0, hai Bezier có cùng đầu mút
C1: C0 + có cùng vector tiếp tuyến tại điểm đầu mút
Trang 37
C2: C1 + có cùng đạo hàm bậc 2 tại điểm đầu mút
Tính liên tục
Liên tục bậc 0
Liên tục bậc 1
Trang 38
Liên tục bậc 2
Tính liên tục
•Liên tục hình học
•G1: tiếp tuyến cùng hướng nhưng không cần cùng độ 
lớn
•G2: cùng tiếp tuyến và cùng độ cong
Trang 39
Thuật toán vẽ đệ qui
p1 p2
p3
Trang 40
p0
l0
r3
l1
l2 l3
r2
r1r0
Thuật toán vẽ đệ qui
321
1
3210
0
10
1
00
4
pp2p
r
8
pp3p3p
r
2
pp
l
pl
++
=
+++
=
+
=
=
Trang 41
33
32
2
3210
3
210
2
pr
2
pp
r
8
pp3p3p
l
4
pp2p
l
=
+
=
+++
=
++
=
Thuật toán vẽ đệ qui
Vẽ Bezier (p0, p1, p2, p3)
Bắt đầu
Nếu Thẳng (p0, p1, p2, p3) thì
Vẽ đoạn thẳng p0p3
Ngược lại
Chia {pi} thành {li} và {ri}
Vẽ Bezier (l0, l1, l2, l3)
Trang 42
Vẽ Bezier (r0, r1, r2, r3)
Kết thúc
ĐƯỜNG CONG HERMITE
Định nghĩa đường cong
Input
2 điểm {p0, p1}
2 vector {v0, v1}
Ouput
Trang 44
p0 p1
0v


1v


Công thức xác định đường cong
p0 p1
0v


1v


Trang 45
p(t) = H03(t)p0 + H13(t)p1 + H23(t)v0 + H33(t)v1
p(t) = (2t3 + 3t2 + 1)p0 + (-2t3 + 3t2)p1 + (t3 – 2t2 + t)v0 + (t3 – t2)v1
t ∈ [0, 1]
hoặc
x(t) = (2t3 + 3t2 + 1)p0x + (-2t3 + 3t2)p1x + (t3 – 2t2 + t)v0x + (t3 – t2)v1x
y(t) = (2t3 + 3t2 + 1)p0y + (-2t3 + 3t2)p1y + (t3 – 2t2 + t)v0y + (t3 – t2)v1y
t ∈ [0, 1]
Một số đường cong Hermite
Trang 46
Đường cong Bezier bậc ba & Hermite
( )
( )B2B3H1
B
0
B
1
H
0
B
3
H
1
B
0
H
0
pp3v
pp3v
pp
pp
−=
−=
=
=
Trang 47
H
0pB
0p
B
1p
B
2p
B
3p H
1p
H
0v
H
1v
Dẫn nhập
Bao nhiêu 
đường cong?
Trang 48
ĐƯỜNG CONG PHỨC
Định nghĩa đường cong phức
Đường cong phức là sự kết hợp của những đường cong 
cơ sở C = {C1, C2, … , Cn}
C2 C3
C
Trang 50
C1
4
Yêu cầu thiết kế đường cong phức
Đối với người thiết kế
1. Dễ vẽ
2. Liên tục
3. Cục bộ
Đối với người lập trình
Trang 51
1. Biểu diễn dễ dàng và hiệu quả
2. Tính toán hiệu quả
Tính liên tục
Liên tục bậc 0
Liên tục bậc 1
Trang 52
Liên tục bậc 2
Phân loại
1. Đường cong Splines
2. Đường cong B-Splines
3. Đường cong Nurbs (NonUniform Rational B-Splines)
Trang 53
CÁC ĐƯỜNG CONG SPLINES
Định nghĩa đường cong Splines
Input
n +1 điểm {P0, P1, ... , Pn}
và một số thông tin khác
Output
C = {C1, C2, …, Cn} với Ci là các đường cong Hermite
P
Trang 55
P0
1
P2
Pn-1
Pn
C1
C2
Cn
Cardinal Splines
- Tham số tension t
Pk
Pk+1
k0
Pp
Pp
=
=
Trang 56
Pk-1
Pk+2
( ) ( )
( ) ( )k2k1
1k1k0
1k1
PP
2
t1
v
PP
2
t1
v
−
−
=
−
−
=
+
−+
+
Ảnh hưởng của tham số tension t
Trang 57
t0
Catmull-Rom Splines
Là trường hợp đặc biệt của Cardinal Splines với t = 0
Pp
Pp
21
10
=
=
P1
P2
P4
Trang 58
2
PP
v
2
PP
v
13
1
02
0
−
=
−
=
P0
P3
Kochanek-Bartels Splines
Là trường hợp tổng quát của Cardinal Splines
- Tham số tension t
- Tham số bias b
- Tham số continuity c
k0 Pp =
Trang 59
( ) ( )( )( ) ( )( )( )[ ]
( ) ( )( )( ) ( )( )( )[ ]1k2kk1k1
k1k1kk0
1k1
PPc1b1PPc1b1t1
2
1
v
PPc1b1PPc1b1t1
2
1
v
Pp
+++
+−
+
−−−+−++−=
−+−+−−+−=
=
Ảnh hưởng của tham số bias b
Trang 60
b0
Natural Splines
Là đường cong liên tục C2
P1
P
v0
v1
v3
Trang 61
P0
P2
3
v2
Natural Splines
P1
P
v0
v1
v3
Trang 62
P0
P2
3
v2
Natural Splines
Trường hợp 1 : 
Biết các vector v0 và vn
( )
( ) 







−
−
















02
0
1
0
PP3
PP3
v
v
v
v
141
141
1
………
………
……………
Trang 63
( )










−
=




















−−
n
2nn
13
n
1n
2
v
PP3
v
v
1
141
……
……………
………
………………
Natural Splines
Trường hợp 2 : 
Đạo hàm bậc hai tại hai điểm P0 và Pn đều bằng 0 
( )
( ) 




−
−












02
01
1
0
PP3
PP3
v
v
141
12
………
…………
Trang 64
( )
( )
( ) 










 −
−
−
=
























−
−−
1nn
2nn
13
n
1n
2
PP3
PP3
PP3
v
v
v
21
141
141
……
…………
………
………………
………
Free Splines
Là đường cong liên tục C0
Trang 65
ĐƯỜNG CONG B-SPLINES
Định nghĩa
Input
n +1 điểm {P0, P1, ... , Pn}, Bậc k – 1, Tập hợp tham số knot 
{t0, t1, … , tn+k}
Output
C = {C1, C2, …, Cn-2} với Ci là các đường cong Bezier
P1 P2
Trang 67
P0 P3 P4
P5C1
C2
C3
Công thức
( ) ( )
[ ]
[ ]t,tt nếu1
Với
1,0t
PtNtp
ni
0i
i
k
i
=
=
∈
=∑
Trang 68
( )
( ) ( ) ( )tN
tt
tt
tN
tt
tt
tN
khác0
tN
1k
1i
1iki
ki1k
i
i1ki
ik
i
1ii1
i
−
+
++
+−
−+
+
−
−
+
−
−
=


 ∈
=
Công thức B-Splines bậc ba đều
P1 P2
P5
p0
p1 p2
p3
3
PP2
p
6
PP4P
p
21
1
210
0
+
=
++
=
Trang 69
P0 P3 P4
6
PP4P
p
3
P2P
p
321
3
21
2
++
=
+
=
Công thức B-Splines bậc hai đều
P1 P2
P5
p2
p1
Pp
2
PP
p 010
=
−
=
Trang 70
P0 P3 P4
p0
2
PP
p 122
11
−
=
ĐƯỜNG CONG HỮU TỈ
Định nghĩa
Là đường cong trong đó các hàm x(t) và y(t) là các 
hàm đa thức hữu tỉ
Trang 72
Đường tròn Đường ellipse
Đường Conic
Dạng chuẩn
yx
Hyperbola
0 b a, 1
b
y
a
x
Ellipse
22
2
2
2
2
>=+
Trang 73
0 a ax4y
Parabola
0 b a, 1
ba
2
22
>=
>=−
Đường Conic
Dạng tham số
( )
( )
( )∞∞−∈
+
=
+
−
=
,t 
t1
t2
bty
t1
t1
atx
Ellipse
2
2
2
Trang 74
( )
( )
( )∞∞−∈
−
=
−
+
=
,t 
t1
t2
bty
t1
t1
atx
Hyperbola
2
2
2
Đường Bezier hữu tỉ bậc hai
Input 
p0(x0, y0) và trọng số w0
p1(x1, y1) và trọng số w1
p2(x2, y2) và trọng số w2
Output
p1,w1
Trang 75
p0,w0
p2,w2
Công thức
Hệ tọa độ thuần nhất
( )
( )
( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) 


 ++










+










+










=










2
2
21
2
10
2
0
2
2
2
2
2
1
1
1
2
1
0
0
0
2
0
xtBxtBxtB
w
y
x
tB
w
y
x
tB
w
y
x
tB
tw
ty
tx
Trang 76
( ) ( ) ( ) 




 ++
++=
2
2
21
2
10
2
0
2
2
21
2
10
2
0
wtBwtBwtB
ytBytBytB
Công thức
Hệ tọa độ đề các
( )
( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) 222121020
2
2
21
2
10
2
0
2
2
21
2
10
2
0
2
2
21
2
10
2
0
xxx
wtBwtBwtB
ytBytBytB
wtBwtBwtB
xtBxtBxtB
ty
tx













++
++
++
++
=





Trang 77
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) 222121020
2
2
2
2
2
1
1
1
2
1
0
0
0
2
0
2
2
21
2
10
2
0
2
22
2
1
12
1
0
02
0
wtBwtBwtB
y
x
wtB
y
x
wtB
y
x
wtB
wtBwtBwtB
y
tB
y
tB
y
tB
++






+





+





=
++




+



+



=
Biểu diễn Conic bằng Bezier hữu tỉ
Đường Ellipse
( )
( )
( )
( )
( ) ( ) ( )
( ) ( ) ( )
0tBatBatB
t1
t2b
t1a
ty
tx
2
2
2
1
2
0
2
2



 ++
+





 −
=





Trang 78
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) 2.tB1.tB1.tB
b
0
.2.tB
b
a
.1.tB
0
a
.1.tB
2tBtBtB
b2tBbtB0tB
2
2
2
1
2
0
2
1
2
1
2
0
2
2
2
1
2
0
2
2
2
1
2
0
++






+





+





=
++
 ++
=
ĐƯỜNG CONG NURBS
Định nghĩa
Là đường cong phức C = {C1, C2, …, Cn-2} với Ci là các 
đường cong Bezier hữu tỉ
Trang 80