Bài giảng Computer graphics and virtual reality - Bài 7: Đường cong trong không gian 3D CURVE - Lê Tấn Hùng

ng tại điểm P0 là đường P0P1 
và tại Pn là đường Pn-1Pn . 
z Đường cong nằm trong đường bao lồi convex hull của 
các điểm kiểm soát.
z This is because each successive Pi(j) is a convex 
combination of the points Pi(j-1) and Pi-1(j-1) . 
z P1 ,P2 ,  ,Pn-1 nằm trên đường cong khi và chỉ khi 
đường cong là đoạn thẳng. 
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
4
Khoa CNTT DHBK Hanoi19
Review:
Bézier Curve Prop’s [1/6]
z We looked at some properties of Bézier curves.
z Generally “Good” Properties
– Endpoint Interpolation
– Smooth Joining
– Affine Invariance
– Convex-Hull Property
z Generally “Bad” Properties
– Not Interpolating
– No Local Control
Khoa CNTT DHBK Hanoi20
Đường bậc ba Spline
z 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
z 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
z 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
Khoa CNTT DHBK Hanoi21
Đường cong bậc ba
Spline
z u0 = 0 với : (u0 ... un-1) uj+1 > uj
z ui+1 = ui + di+1
z C0 để không có sự gián đoạn giữa hai đoạn cong. 
z 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. 
z C2 đạo hàm bậc hai liên tục của đường cong tại điểm nối
Khoa CNTT DHBK Hanoi22
z 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. 
z 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
Khoa CNTT DHBK Hanoi23
Đường cong B-spline
z Đườ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.
Khoa CNTT DHBK Hanoi24
B-Splines:
The Idea [1/2]
z The repeated-lirping idea that produced the Bézier 
curves has the drawbacks that is produces polynomials 
with high degree that are nonzero almost everywhere.
– Using functions defined in pieces, we can fix these two.
z Start: An order-1 B-Spline has blending functions that are 
always either 1 or 0. When a function is 1, all the rest are 
zero.
– So an order-1 B-spline is just a sequence of points.
– Any number of control points may be used.
z Now we make higher-order B-splines using a repeated-
lirping procedure.
– But this time, we can use any number of control points.
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
5
Khoa CNTT DHBK Hanoi25
B-Splines:
The Idea [2/2]
z We form an order-2 B-Spline by lirping between the order-1 blending 
functions.
– As discussed, we get functions that start at 0, ramp up to 1 and back 
down, then stay at zero. Each function is 0 most of the time.
– So each blending function is defined in pieces. Each piece is a 
polynomial of degree 1 (graph is a line).
– So an order-2 B-spline is just the control polygon.
– Again, any number of control points may be used.
z We form an order-3 B-Spline by lirping between the order-2 blending 
functions.
– Now blending functions are smooth. They start at 0, curve up to 1 then 
back down. Again, each function is 0 most of the time.
– Again, each blending function is defined in pieces. Each piece is a 
polynomial of degree 2.
z We continue this repeated-lirping procedure to define B-splines of 
higher order.
– See the blue book for details and graphs. Khoa CNTT DHBK Hanoi26
Types of B-Splines Approximation Curves Used
B-Spline approximations can be classified based on the 
spacing of the knot vector and the use of weights. 
1. Uniform/Periodic B-splines : The spacing is
unform and the knots (control points) are equispaced e.g. 
[0,1,2,3,4,5] These have satisfactory smoothness but lack 
local control and the starting and ending poits are ill 
defined as above. 
2. Non-periodic: The knots are repeated at the ends m 
times and the interior is equispaced. e.g. [0 0 0 1 2 3 3 3 
] These can be used to force the control point to start 
and finish at a control point. 
3. Non-uniform B-Splines : The spacing is non-
uniform and or repeated knots e.g. [0 1 1 2 4 5 6 6 
] These can be used to obtain local control
B-Splines
Khoa CNTT DHBK Hanoi27
B-spline
z Ni,k(u) đa thức B-Spline cơ bản
z Với n+ 1 sô điểm kiểm soát
z Pi điểm kiểm soát thứ i
z k bậc của đường cong 1<k<n+2
z Ui vector nút của đường cong 
U=[U1,U2...Un+k+1]
i
n
i
ki PuNuP ∑
=
=
0
, ).()(
)(
)(
)()()()( 1,
21
1
1,1
1
1
, uNUU
uUuN
UU
UuuN ki
kii
i
ki
kii
ki
ki −
−++
+
−−
−+
−+
−
−+−
−=
⎩⎨
⎧ ∈= +
others0
],[1
)( 11,
ii
i
uuu
uN
Khoa CNTT DHBK Hanoi28
Khoa CNTT DHBK Hanoi29
Đặc điểm
z 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.
z 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.
z Tính chất bao lồi của đa giác kiểm soát và tính chất chuẩn được thoa 
mãn. 
z 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: 
z 0 ≤ u ≤ n - k + 2
1(u)N
n
0i
ki, =∑
=
Khoa CNTT DHBK Hanoi30
B Spline -Đều và tuần hoàn
z 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 
z Ví dụ: [ 0 1 2 3 4 5 ] với ∇ xác định = 1
z [ -2 -1/2 1 5/2 4 ] với ∇ xác định = 3/2
z Với cấp là k, số điểm kiểm soát là n+1 thì vecto nút đều là 
z U=[0 1 2 ...n+k] khoảng tham số (k-1)≤u≤(n+1).
z Khi vecto nút là đều thì ta có Ni,k(u)=Ni-1,k(u-
1)=Ni+1,k(u+1)
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
6
Khoa CNTT DHBK Hanoi31 Khoa CNTT DHBK Hanoi32
Không tuần hoàn
Open – Non Uniform
z Một vector không tuần hoàn hoặc mở
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
z 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.
z 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
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
Khoa CNTT DHBK Hanoi33
B-Splines:
Properties
z The most used B-splines are:
– Order 3 (“quadratic B-splines”).
z Smooth.
– Order 4 (“cubic B-splines”).
z Smoother, but control is a little less local.
z B-splines have the following properties.
– An order-k B-spline has blending functions that are defined in pieces, 
using polynomials of degree k–1.
z This is true for any number of control points. We can choose the number of 
control points and the polynomial degree separately. ☺
– B-splines are affine invariant (of course).
– They have the convex-hull property. ☺
– They have local control. ☺
– A B-spline (of order 3 or more) does not interpolate any of its control 
points. / But we can deal with this 
Khoa CNTT DHBK Hanoi34
Kết luận
z B-spline là một dòng của Bezier
z 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
z 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.
z Khi tồn tại anh hưởng cục bộ càng lớn và đường cong phai đi qua điểm 
đó.
z Chúng ta có thể thay đổi hình dạng đường cong B-spline bằng cách:
z Thay đổi kiểu vecto nút : đều tuần hoàn, mở, không đều
z Thay đổi cấp k của đường cong
z Thay đổi số đỉnh và vị trí các đỉnh đa giác kiểm soát
z Sử dụng các điểm kiểm soát trùng nhau
Khoa CNTT DHBK Hanoi35
Non-uniform Rational B-Splines(NURBS)
The last 3 types are good for representing free form curves but also introduce 
unnecessary approximations in the representation of conic sections. NURBS build on 
non-uniform B-Splines and introduce a weight function to obtain an approximation 
that retains all the advantages of the non-uniform B-Splines and is also capable of 
exact representation of conic sections (circles, parabolas etc.).The general form is 
given below: 
The curve is described as rational since it is expressed as the ratio of two 
polynomials. wi defines a weight function. If wi is set to 1 we get back the non-
uniform B-Spline. Other values of the wi can be used to produce curves for straight 
line, parabola, ellipse and hyperbola. 
Khoa CNTT DHBK Hanoi36
Other Splines:
NURBS, etc.
z There are any number of other types of splines.
– Often we want a very general type of curve that will do whatever we want.
z One such type of curve that has been very successful is the NURBS.
– NURBS = Non-Uniform Rational B-Spline.
– A NURBS is defined using rational functions.
z A rational function is a polynomial divided by a polynomial.
– Control points can be given weights, so some are more important than others.
– NURBS curves (and surfaces) are built into GLU, but can be rather complex to 
use.
z One important issue when defining curves and surfaces:
– In advanced rendering the technique of ray tracing is often used.
– In ray tracing, we determine the color of a pixel by tracing a ray of light backward 
from the viewer’s eye, through the pixel, and we see where the ray came from.
– In order to do ray tracing efficiently, we must be able to test quickly whether a 
particular ray hits a particular object and, if so, where.
– Types of surfaces in which this test can be done quickly will be more useful in 3-D 
graphics.
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
7
Khoa CNTT DHBK Hanoi37