Bài giảng Computer Graphics - Bài: Đường cong trong không gian 3D CURVE

ise 0
 1 1
1,
kk
k
ttt
tB
B-Spline Blending Functions
„ The recurrence relation starts with the 1st order B-splines, 
just boxes, and builds up successively higher orders
„ This algorithm is the Cox - de Boor algorithm
( ) ( )
( )tB
tt
tt
tB
tt
tttB
dk
kdk
dk
dk
kdk
k
dk
1,1
1
1,
1
,
−+
++
+
−
−+




−
−
+



−
−=
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
9
(c) SE/FIT/HUT 2002 49
Bk,1
B 0,1
0
0.2
0.4
0.6
0.8
1
1.2
-3
-2
.8
-2
.6
-2
.4
-2
.2 -2
-1
.8
-1
.6
-1
.4
-1
.2 -1
-0
.8
-0
.6
-0
.4
-0
.2 0 0.
2
0.
4
0.
6
0.
8 1
t
B
0,
1(
t)
B 2,1
0
0.2
0.4
0.6
0.8
1
1.2
-3 -2 .
8
-2 .
6
-2 .
4
-2 .
2 -2 -1 .
8
-1 .
6
-1 .
4
-1 .
2 -1 -0 .
8
-0 .
6
-0 .
4
-0 .
2 0 0.2 0.4 0.6 0.8 1
t
B
2,
1(
t)
B 3,1
0
0.2
0.4
0.6
0.8
1
1.2
-3 -2 .8 -2 .6 -2 .4 -2 .2 -
2
-1 .8 -1 .6 -1 .4 -1 .2 -
1
-0 .8 -0 .6 -0 .4 -0 .2
0 0.2 0.4 0.6 0.8 1
t
B
3,
1(
t)
B 1,1
0
0.2
0.4
0.6
0.8
1
1.2
-3 -2.
8
-2.
6
-2.
4
-2.
2 -2 -1.
8
-1.
6
-1.
4
-1.
2 -1 -0.
8
-0.
6
-0.
4
-0.
2 0 0.2 0.4 0.6 0.8 1
t
B
1,
1(
t)
(c) SE/FIT/HUT 2002 50
Bk,2
B 0,2
0
0.2
0.4
0.6
0.8
1
1.2
-3
-2
.8
-2
.6
-2
.4
-2
.2 -2
-1
.8
-1
.6
-1
.4
-1
.2 -1
-0
.8
-0
.6
-0
.4
-0
.2 0 0.
2
0.
4
0.
6
0.
8 1
t
B
0,
2(
t)
B 1,2
0
0.2
0.4
0.6
0.8
1
1.2
-3
-2
.8
-2
.6
-2
.4
-2
.2 -2
-1
.8
-1
.6
-1
.4
-1
.2 -1
-0
.8
-0
.6
-0
.4
-0
.2 0 0.
2
0.
4
0.
6
0.
8 1
t
B
1,
2(
t)
B 2,2
0
0.2
0.4
0.6
0.8
1
1.2
-3
-2
.8
-2
.6
-2
.4
-2
.2 -2
-1
.8
-1
.6
-1
.4
-1
.2 -1
-0
.8
-0
.6
-0
.4
-0
.2 0 0.
2
0.
4
0.
6
0.
8 1
t
B
2,
2(
t)


−<≤−−−
−<≤−+=
12 1
23 3
)(2,0 tt
tt
tB
(c) SE/FIT/HUT 2002 51
Bk,3
B 0,3
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
-3
-2
.8
-2
.6
-2
.4
-2
.2 -2
-1
.8
-1
.6
-1
.4
-1
.2 -1
-0
.8
-0
.6
-0
.4
-0
.2 0 0.
2
0.
4
0.
6
0.
8 1
t
B
0,
3(
t)
B 1,3
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
-3 -2.
8
-2.
6
-2.
4
-2.
2 -2 -1.
8
-1.
6
-1.
4
-1.
2 -1 -0.
8
-0.
6
-0.
4
-0.
2 0 0.2 0.4 0.6 0.8 1
t
B1
,3
(t)
( )



<≤−
−<≤−−−−
−<≤−+
=
01 
12 362
23 3
2
1)(
2
2
2
3,0
tt
ttt
tt
tB
(c) SE/FIT/HUT 2002 52
B0,4
B 0,4
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
-3
-2
.8
-2
.6
-2
.4
-2
.2 -2
-1
.8
-1
.6
-1
.4
-1
.2 -1
-0
.8
-0
.6
-0
.4
-0
.2 0 0.
2
0.
4
0.
6
0.
8 1
t
B
0,
4(
t)
(c) SE/FIT/HUT 2002 53
B0,4
( )
( )


<≤−
<≤−+−+
−<≤−−−−−
−<≤−+
=
10 1
01 1333
12 521153
23 3
6
1)(
3
23
23
3
4,0
tt
tttt
tttt
tt
tB
Note that the functions given on slides 5 and 6 are translates of this 
function obtained by using (t-1), (t-2) and (t-3) instead of just t, and then 
selecting only a sub-range of t values for each function
(c) SE/FIT/HUT 2002 54
B Spline - Đều và tuần hoàn
„ 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)
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
10
(c) SE/FIT/HUT 2002 55
Không tuần hoàn
Open – Non Uniform
„ 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
„ 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
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) SE/FIT/HUT 2002 56
B-Splines:
Properties
„ The most used B-splines are:
„ Order 3 (“quadratic B-splines”).
• Smooth.
„ Order 4 (“cubic B-splines”).
• Smoother, but control is a little less local.
„ 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.
• 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 
(c) SE/FIT/HUT 2002 57
Kết luận
„ 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
(c) SE/FIT/HUT 2002 58
Rational Curves
„ Each point is the ratio of two curves
„ Just like homogeneous coordinates:
„ NURBS: x(t), y(t), z(t) and w(t) are non-uniform B-splines
„ Advantages:
„ Perspective invariant, so can be evaluating in screen space
„ Can perfectly represent conic sections: circles, ellipses, etc
• Piecewise cubic curves cannot do this


→
)(
)(,
)(
)(,
)(
)()](),(),(),([
tw
tz
tw
ty
tw
txtwtztytx
(c) SE/FIT/HUT 2002 59
Rational Spline - NURBS
„ A Rational Spline is like a B-Spline 
but the designer can add weightings 
to the blending functions to modify 
the curve. 
„ The blending functions produce a 
ratio of the polynomials used.
∑
=
=
L
k
kk tRPP t
0
)()(
∑
=
= L
k
mkk
mkk
k
t
t
t
Nw
NwR
0
,
,
)(
)(
)(
(c) SE/FIT/HUT 2002 60
OpenGL and NURBS
„ NURBS: Non-uniform Rational B-splines
„ The curved surface of choice in CAD packages
„ Support routines are part of the GLu utility library
„ Allows you to specify how they are rendered:
„ Can use points constantly spaced in parametric space
„ Can use various error tolerances - the good way!
„ Allows you to get back the lines that would be drawn
„ Allows you to specify trim curves
„ Only for surfaces
„ Cut out parts of the surface - in parametric space
CNTT-DHBK Hanoi
hunglt@it-hut.edu.vn
11
(c) SE/FIT/HUT 2002 61
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. 
(c) SE/FIT/HUT 2002 62
Other Splines:
NURBS, etc.
„ There are any number of other types of splines.
„ Often we want a very general type of curve that will do whatever we want.
„ 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.
• 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.
„ 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.
(c) SE/FIT/HUT 2002 63
Tính chất cả đường cong đa thức
„ 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. 
„ Ví dụ Bézier curve, for instance, lies within the convex hull (polygon 
envelope) of the set of control points. 
„ Đ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.
(c) SE/FIT/HUT 2002 64
How to Choose a Spline
„ Hermite curves are good for single segments where you know the 
parametric derivative or want easy control of it
„ Bezier curves are good for single segments or patches where a user 
controls the points
„ B-splines are good for large continuous curves and surfaces
„ NURBS are the most general, and are good when that generality is useful, 
or when conic sections must be accurately represented (CAD)