Bài giảng Đồ họa hiện thực ảo - Bài 7: Đường cong trong không gian 3D Curve - Lê Tấn Hùng
Đường cong - Curve
Đường cong trong không gian
ꢀ Why use curves? Quỹ đạo chuyển động của 1 điểm trong
3D CURVE
không gian
ꢀ
Đường cong biểu diễn Điểm -curve represents points:
ꢀ
Điểm Biểu diễnvà kiểm soát đường cong -Points represent-
and control-the curve.
ꢀ
Cách tiếp cận này là cơ sở của lĩnh vực Computer Aided Geometric
Design (CAGD).
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
2
4
6
Phân loại
Biểu diễn Đường cong
ꢀ
Tường minh y=f(x)
ꢀ
Trên cơ sở ràng buộc giữa điểm và đường trong cả ứng dụng khoa học và
ꢀ
y = f(x), z = g(x)
thiết kế ta co thể phân làm 2 loại:
ꢀ
Xấp xỉ-Approximation -
ꢀ
ꢀ
not invariant with rotation
•
rotation might require further segment
breaking
ꢀ
Được ứng dụng trong mô hình hoá hình học
Nội suy-Interpolation
ꢀ
ꢀ
problem with curves with vertical tangents
•
infinite slope is difficult to represent
ꢀ
Không tường minh f(x,y)=0 - Implicit equations:
ꢀ
f(x,y,z) = 0
ꢀ
equation may have more solutions than we
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“.
want
•
circle: x² + y² = 1, half circle: ?
ꢀ
problem to join curve segments together
•
difficult to determine if their tangent
directions agree at their joint point
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
3
Đường cong tham biến
Biểu diễn các đường cong tham
Parametric Curves
ꢀ
ꢀ We have seen the parametric form for a line:
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
x = x(t), y = y(t), z = z(t)
x = x0t + (1−t)x1
overcomes problems with explicit and implicit forms
no geometric slopes (which may be infinite)
parametric tangent vectors instead (never infinite)
a curve is approximated by a piecewise polynomial curve
y = y0t + (1−t)y1
z = z0t + (1−t)z1
ꢀ Note that x, y and z are each given by an equation that
involves:
ꢀ
Define a parameter space
ꢀ
ꢀ
1D for curves
2D for surfaces
ꢀ
The parameter t
ꢀ
ꢀ
Define a mapping from parameter space to 3D points
ꢀ
Some user specified control points, x0 and x1
ꢀ This is an example of a parametric curve
ꢀ
A function that takes parameter values and gives back 3D points
The result is a parametric curve or surface
Mapping F :t → (x, y, z)
0
1
t
(c) SE/FIT/HUT 2002
5
(c) SE/FIT/HUT 2002
Đường cong đa thức bậc ba
Đường cong bậc 3
ꢀ
Phải đảm bảo là đường cong không gian với 3 trục toạ độ x, y, z
3
ꢀ
ꢀ
ꢀ
x = a1 + b1u + c1u2 + d1u
ꢀ
tránh được những tính toán phức tạp và những phần nhấp nhô ngoài ý
y = a2 + b2u + c2u2 + d2u
3
muốn xuất hiện ở những đường đa thức bậc cao
Why cubic?
3
z = a3 + b3u + c3u2 + d3u
ꢀ
ꢀ
Với 3 điểm P0, P1, P2, P3 phương trình
xác định
P'1
p3
p2
P1
P'0
P1
P0
P0
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
7
8
Hermite Spline
Đường cong Hermite
ꢀ p = p(u) = k0 + k1u + k2u2 + k3u3
p(u) = ∑kiui i∈n
ꢀ
A spline is a parametric curve defined by control points
ꢀ
The term spline dates from engineering drawing, where a spline was a piece
of flexible wood used to
ꢀ
The control points are ad
ꢀ
ꢀ
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
A Hermite spline is a curve for which the user provides:
ꢀ 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].
ꢀ We have constraints:
ꢀ
The endpoints of the curve
ꢀ
ꢀ
ꢀ
ꢀ
The curve must pass through p0 when u=0
The derivative must be p’0 when u=0
The curve must pass through p1 when u=1
The derivative must be p’1 when u=1
ꢀ
The parametric derivatives of the curve at the endpoints
•
The parametric derivatives are dx/dt, dy/dt, dz/dt
ꢀ
That is enough to define a cubic Hermite spline, more derivatives are required
for higher order curves
(c) SE/FIT/HUT 2002
9
(c) SE/FIT/HUT 2002
10
Basis Functions
ꢀ
A point on a Hermite curve is obtained by multiplying each control point
by some function and summing
ꢀ
ꢀ
Thay vào:
p = p(u) = p0(1-3u +2u ) + p1(3u -2u )
3
ꢀ
The functions are called basis functions
2
3
2
3
2
3
2
+ p0’(u-2u +u ) + p1’(-u +u )
p = p(u) = [ 1 u u2 u3 ]
(c) SE/FIT/HUT 2002
11
(c) SE/FIT/HUT 2002
12
Đường cong Bezier
ꢀ 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.(Hermit)
ꢀ 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
ꢀ 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ố (Hermite).
Paul Bezier, RENAULT, 1970 đường và bề mặt UNISURF
ꢀ p0’ = 3(p1 – p0)
ꢀ p3’ = 3(p3 – p2)
ꢀ
ꢀ p = p(u) = p0(1-3u2+2u3) + p1(3u2-2u3) + p0’(u-2u2+u3) + p1’(-
u2 + u3)
ꢀ p = p(u) = p0(1 - 3u + 3u2 - u3) + p1(3u-6u2-3u3)
+ p2(3u2 - 3u3) + p3u3
(c) SE/FIT/HUT 2002
13
15
17
(c) SE/FIT/HUT 2002
14
Biểu diễn Ma trận
Ưu điểm
1.2
1
ꢀ dễ dàng kiểm soát hi`nh dạng của đường cong hơn vector tiếp
số điểm trung gian tuỳ ý( số
0.8
0.2
0
B0
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 đó
1
0
3
0
0
0
0
0
1
p
0
−3
3
p1
p
2
3
p = p(u) = [ 1 u u u ]
−6
3
3
2
−1
−3
p3
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
16
Example
Bezier Curves
Sub-Dividing Bezier Curves
M12
P2
M012
M0123
M123
M01
M23
P0
P3
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
18
Sub-Dividing Bezier Curves
Sub-Dividing Bezier Curves
P1
P2
ꢀ
Step 1: Find the midpoints of the lines joining the original control vertices.
Call them M01, M12, M23
ꢀ
Step 2: Find the midpoints of the lines joining M01, M12 and M12, M23. Call
them M012, M123
ꢀ
ꢀ
Step 3: Find the midpoint of the line joining M012, M123. Call it M0123
The curve with control points P0, M01, M and M
exactly follows the
original curve from the point with t=0 to0t1h2e point0w12i3th t=0.5
ꢀ
The curve with control points M0123 , M123 , M23 and P3 exactly follows the
original curve from the point with t=0.5 to the point with t=1
P0
P3
(c) SE/FIT/HUT 2002
19
(c) SE/FIT/HUT 2002
20
22
24
de Casteljau’s Algorithm
Biểu thức Bezier-Bernstain
ꢀ Tổng quát hoá với n +1 điểm kiểm soát
ꢀ
You can find the point on a Bezier curve for any parameter value t with a similar
algorithm
n
ꢀ
Say you want t=0.25, instead
n
P2
P1
′
p (u) = n
B
i,n−1(u)( pi+1 − P)
∑
i
i=0
M23
Bi,n (u) = C(n,i)ui(1− u)n−i
t=0.25
M01
P0
ꢀ p0 ... pn : vector vị trí của đa giác n+1 đỉnh
n!
C(n,i) =
i!(n − i)!
P3
(c) SE/FIT/HUT 2002
21
(c) SE/FIT/HUT 2002
Review:
Tính chất
Bézier Curve Prop’s [1/6]
We looked at some properties of Bézier curves.
Generally “Good” Properties
ꢀ
ꢀ
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
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
Endpoint Interpolation
Smooth Joining
Affine Invariance
ꢀ Tiếp tuyến của đường cong tại điểm P0 là đường P0P1 và tại
Pn là đường Pn-1Pn .
Convex-Hull Property
ꢀ Đường cong nằm trong đường bao lồi convex hull của các
ꢀ
Generally “Bad” Properties
điểm kiểm soát.
ꢀ
Not Interpolating
No Local Control
ꢀ This is because each successive Pi(j) is a convex
combination of the points Pi(j-1) and Pi-1(j-1) .
ꢀ P1 ,P2 , … ,Pn-1 nằm trên đường cong khi và chỉ khi
đường cong là đoạn thẳng.
ꢀ
(c) SE/FIT/HUT 2002
23
(c) SE/FIT/HUT 2002
Problem with Bezier Curves
ꢀ To make a long continuous curve with Bezier segments
requires using many segments
Invariance
ꢀ
Translational invariance means that translating the control points and then
evaluating the curve is the same as evaluating and then translating the curve
ꢀ
Rotational invariance means that rotating the control points and then evaluating
the curve is the same as evaluating and then rotating the curve
ꢀ Maintaining continuity requires constraints on the control
ꢀ
ꢀ
These properties are essential for parametric curves used in graphics
It is easy to prove that Bezier curves, Hermite curves and everything else we will
point positions
study are translation and rotation invariant
ꢀ
The user cannot arbitrarily move control vertices and automatically
maintain continuity
ꢀ
Some forms of curves, rational splines, are also perspective invariant
ꢀ
Can do perspective transform of control points and then evaluate the curve
ꢀ
ꢀ
The constraints must be explicitly maintained
It is not intuitive to have control points that are not free
(c) SE/FIT/HUT 2002
25
(c) SE/FIT/HUT 2002
26
Longer Curves
Piecewise Bezier Curve
ꢀ
A single cubic Bezier or Hermite curve can only capture a small class of curves
P0,1
P0,2
ꢀ
At most 2 inflection points
ꢀ
One solution is to raise the de
not”
ꢀ
Allows more control, at the
polynomials
P1,3
ꢀ
Control is not local, one control point influences entire curve
P0,3
P1,0
ꢀ
Alternate, most common solution is to join pieces of cubic curve together into
piecewise cubic curves
ꢀ
ꢀ
ꢀ
Total curve can be broken into pieces, each of which is cubic
Local control: Each control point only influences a limited part of the curve
Interaction and design is much easier
P1,2
P1,1
(c) SE/FIT/HUT 2002
27
(c) SE/FIT/HUT 2002
28
Continuity
Đường bậc ba Spline
ꢀ 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
ꢀ
When two curves are joineef
across the boundary (the knot)
ꢀ
ꢀ
ꢀ
ꢀ
C0, “C-zero”, point-wise continuous, curves share the same point where they
join
C1, “C-one”, continuous derivatives, curves share the same parametric
derivatives where they join
ꢀ
C2, “C-two”, continuous second derivatives, curves share the same parametric
second derivatives where they join
Higher orders possible
ꢀ
ꢀ
Question: How do we ensure that two Hermite curves are C1 across a
ꢀ
knot?
Question: How do we ensure that two Bezier curves are C0, or C1, or C2
across a knot?
(c) SE/FIT/HUT 2002
29
(c) SE/FIT/HUT 2002
30
Đường cong bậc ba
Achieving Continuity
Spline
ꢀ
For Hermite curves, the user specifies the derivatives, so C1 is achieved
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
u0 = 0 với : (u0 ... un-1)
ui+1 = ui + di+1
0 để 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.
uj+1 > uj
simply by sharing points and derivatives across the knot
ꢀ
For Bezier curves:
C
ꢀ
They interpolate their endpoints, so C0 is achieved by sharing control points
ꢀ
The parametric derivative is a constant multiple of the vector joining the
first/last 2 control points
C
2 đạo hàm bậc hai liên tục của đường cong tại điểm nối
ꢀ
ꢀ
So C1 is achieved by setting P0,3=P1,0=J, and making P0,2 and J and P1,1
collinear, with J-P0,2=P1,1-J
C
2 comes from further constraints on P0,1 and P1,2
(c) SE/FIT/HUT 2002
31
33
35
(c) SE/FIT/HUT 2002
32
Bezier Continuity
B-splines
ꢀ
B-splines automatically take care of continuity, with exactly one control
P0,1
P0,2
vertex per curve segment
be different (linear, quadratic,
P0,0
r non-uniform
J
ꢀ
We will only look closely at uniform B-splines
ꢀ
With uniform B-splines, continuity is always one degree lower than the
degree of each curve piece
P1,2
ꢀ
Linear B-splines have C0 continuity, cubic have C2, etc
P1,1
Disclaimer: PowerPoint curves are not Bezier curves, they are
interpolating piecewise quadratic curves! This diagram is an
approximation.
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
34
B-Splines:
The Idea [1/2]
Đường cong B-spline
ꢀ Đườ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.
ꢀ
ꢀ
ꢀ
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.
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.
ꢀ
Now we make higher-order B-splines using a repeated-lirping procedure.
ꢀ
But this time, we can use any number of control points.
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
36
B-Splines:
B-Splines
The Idea [2/2]
ꢀ
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
Types of B-Splines Approximation Curves Used
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).
B-Spline approximations can be classified based on the
spacing of the knot vector and the use of weights.
ꢀ
ꢀ
So an order-2 B-spline is just the control polygon.
Again, any number of control points may be used.
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
ꢀ
ꢀ
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.
ꢀ
We continue this repeated-lirping procedure to define B-splines of higher order.
]
These can be used to force the control point to start
ꢀ
See the blue book for details and graphs.
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
]
(c) SE/FIT/HUT 2002
37
(c) SE/FIT/HUT 2002
38
Ví dụ: Uniform Cubic B-spline on
[0,1]
Basis Functions on [0,1]
ꢀ
ꢀ
Four control points are required to define the curve for 0≤t<1 (t is the
ꢀ
Does the curve interpolate its endpoints?
Does it lie inside its convex hull?
parameter)
0.4
0.3
0.2
0.1
0
ꢀ
Not surprising for a cubic curv
The equation looks just like a B
ꢀ
Also called blending functions
1
P (t ) = P
1−3t +3t 2 −t 3
( )
make the curve
0 6
1
+ P
4 − 6t 2 +3t 3
( )
1 61
1
B0,4
B3,4
3
P (t ) = P Bi ,4 (t )
∑
i
i
=0
+ P
1+3t +3t 2 −3t 3
( )
2 6
1
1
1
61
1
1
= P
(
1−3t +3t 2 −t 3
)
+ P
(
4 − 6t 2 +3t 3
)
+ P
(
1+3t +3t 2 −3t 3
)
+ P
( )
t 3
0 6
2 6
3 6
+ P
( )
t 3
t
3 6
(c) SE/FIT/HUT 2002
39
(c) SE/FIT/HUT 2002
40
Uniform Cubic B-spline on [0,1)
Uniform - B-spline
ꢀ
ꢀ
ꢀ
The blending functions sum to one, and are positive everywhere
The curve lies inside its convex hull
The curve does not interpolate its endpoints
Requires hacks or non-uniform B-splines
There is also a matrix form for the curve:
1
0
u∈[ui ,ui+1]
others
P(u) =
Ni,k (u).P
i
Ni,1(u) =
∑
ꢀ
i=0
ꢀ
(u −Ui+1−k
Ui −Ui+1−k
)
(Ui+1 − u)
(Ui+1 −Ui+2−k
N
i,k (u) =
Ni−1,k−1 (u) +
Ni,k−1 (u)
)
ꢀ 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]
−1
3
−3
1
3
− 6
3
−3 1 3
t
t 2
0
3
0
4
1
6
P (t ) =
[
P0 P1 P2 P3
]
1
t
0
0
1
(c) SE/FIT/HUT 2002
41
(c) SE/FIT/HUT 2002
42
Using Uniform B-splines
Uniform Cubic B-spline Blending Functions
ꢀ At any point t along a piecewise uniform cubic B-spline, there
B0,4
B1,4
B2,4
B3,4
B4,4
B5,4
B6,4
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
are four non-zero blending functions
ꢀ Each of these blending functions is a translation of B0,4
ꢀ Consider the interval 0≤t<1
ꢀ
ꢀ
ꢀ
ꢀ
We pick up the 4th section of B0,4
We pick up the 3rd section of B1,4
We pick up the 2nd section of B2,4
We pick up the 1st section of B3,4
-3 -2.5 -2 -1.5 -1 -0.5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
t
(c) SE/FIT/HUT 2002
43
(c) SE/FIT/HUT 2002
44
46
48
Computing the Curve
n
X
(t
)
=
P Bk,4
(t
)
∑
k
k=0
0.25
0.2
0.15
0.1
0.05
0
P1B1,4
44,4
P0B0,4
P2B2,4
P6B6,4
P3B3,4
P5B5,4
t
The curve can’t start until there are 4 basis functions active
(c) SE/FIT/HUT 2002
45
(c) SE/FIT/HUT 2002
Đặc điểm
B-Spline Blending Functions
ꢀ B-spline không đi qua h
t − tk
k+d −1 − tk
1
0
tk t k+1
otherwise
(
t
)
=
Bk,d −1
(
t
)
)
+
Bk,d
Bk,1 t =
( )
được dùng là tuyến tính.
t
ꢀ 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.
tk+d − t
Bk+1,d −1 t
(
tk+d − tk+1
ꢀ 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
ꢀ Tính chất bao lồi của đa giác kiểm soát và tính chất chuẩn
n
được thoa mãn.
N
i,k (u) =1
∑
i=0
ꢀ 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) SE/FIT/HUT 2002
47
(c) SE/FIT/HUT 2002
Bk,1
Bk,2
B
0,2
B
1,1
B 0,1
B 1,2
1.2
1.2
1.2
1
1.2
1
1
1
0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
0.2
0
t
t
t
t
B
2,2
B
3,1
B
2,1
1.2
1
1.2
1
1.2
1
t + 3
− 3 ≤ t < −2
0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
0.2
0
0.8
0.6
0.4
0.2
0
B0,2 (t) =
−1− t − 2 ≤ t < −1
t
t
t
(c) SE/FIT/HUT 2002
49
51
53
(c) SE/FIT/HUT 2002
50
Bk,3
B0,4
B 0,3
B 0,4
B 1,3
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0.8
0.1
0
0.4
0.3
0.2
0.1
0
t
t
2
(
t + 3
)
− 3 ≤ t < −2
1
2
B0,3(t) =
− 2t2 − 6t − 3 − 2 ≤ t < −1
t
t2
−1≤ t < 0
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
52
B0,4
B Spline - Đều và tuần hoàn
t + 3 3
)
− 3 ≤ t < −2
(
ꢀ 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
1
6
− 3t3 −15t2 − 21t − 5 − 2 ≤ t < −1
B
0,4 (t) =
3t3 + 3t2 − 3t +1
−1≤ t < 0
0 ≤ t <1
3
ꢀ 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
(
1− t
)
ꢀ 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).
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
ꢀ Khi vecto nút là đều thì ta có Ni,k(u)=Ni-1,k(u-1)=Ni+1,k(u+1)
(c) SE/FIT/HUT 2002
(c) SE/FIT/HUT 2002
54
Không tuần hoàn
B-Splines:
Properties
Open – Non Uniform
ꢀ
The most used B-splines are:
ꢀ
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ấp
số lượng nút (m
Vector nút
không tuần
hoàn
ꢀ
Order 3 (“quadratic B-splines”).
Smooth.
Order 4 (“cubic B-splines”).
Smoother, but control is a little less local.
k
= n + k)
•
ꢀ
2
3
4
6
7
8
[0 0 1 2 3 3]
[0 0 0 1 2 2 2]
[0 0 0 0 1 1 1 1]
•
ꢀ
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. ☺
Cách tính Ui
Ui = 0
1=<i<=k
A B-spline (of order 3 or more) does not interpolate any of its control points. ꢁ But we
Ui = i-k
k+1<i<=n+1
can deal with this …
Ui = n-k+2 n+1<i<=n+k+1
(c) SE/FIT/HUT 2002
55
(c) SE/FIT/HUT 2002
56
58
60
Kết luận
B-spline là một dòng của Bezier
Rational Curves
ꢀ
ꢀ
ꢀ
Each point is the ratio of two curves
Just like homogeneous coordinates:
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
x(t) y(t) z(t)
,
,
ꢀ
Khi bậc của đa thức giảm sự
w(t) w(t) w(t)
ꢀ
NURBS: x(t), y(t), z(t) and w(t) are non-uniform B-splines
ràng hơn.
ꢀ
Advantages:
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
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
Perspective invariant, so can be evaluating in screen space
Can perfectly represent conic sections: circles, ellipses, etc
Piecewise cubic curves cannot do this
ꢀ
•
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
57
(c) SE/FIT/HUT 2002
Rational Spline - NURBS
OpenGL and NURBS
ꢀ
A Rational Spline is like a B-Spline
but the designer can add weightings
to the blending functions to modify
the curve.
NURBS: Non-uniform Rational B-splines
L
ꢀ
The curved surface of choice in CAD packages
(t ) =
(t )
∑
P
P k Rk
ꢀ
ꢀ
Support routines are part of the GLu utility library
Allows you to specify how they are rendered:
k =0
ꢀ
Can use points constantly spaced in parametric space
Can use various error tolerances - the good way!
ꢀ
(t)
wk Nk,m
ꢀ
The blending functions produce a
ꢀ
ꢀ
Allows you to get back the lines that would be drawn
Allows you to specify trim curves
(t) =
Rk
L
ratio of the polynomials used.
(t)
∑
wk Nk,m
ꢀ
ꢀ
Only for surfaces
k=0
Cut out parts of the surface - in parametric space
(c) SE/FIT/HUT 2002
59
(c) SE/FIT/HUT 2002
Other Splines:
NURBS, etc.
Non-uniform Rational B-Splines(NURBS)
ꢀ
There are any number of other types of splines.
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:
ꢀ
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.
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.
ꢀ
ꢀ
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
61
(c) SE/FIT/HUT 2002
62
Tính chất cả đường cong đa thức
How to Choose a Spline
ꢀ
Tham biến – parametric sử dụng tham biến ngoài để biểu diễn cho các
ꢀ
Hermite curves are good for single segments where you know the
parametric derivative or want easy control of it
tham biến trong
ꢀ
Độ mượt - smooth. Với đư
continuity của đường cong
kiểm soát-control point. Vớ
second derivative hay độ cong được đảm bảo curvature.
ments or patches where a user
ꢀ
ꢀ
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)
ꢀ
Độ 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
63
(c) SE/FIT/HUT 2002
64
11 trang
15500
Free
Bạn đang xem tài liệu "Bài giảng Đồ họa hiện thực ảo - Bài 7: Đường cong trong không gian 3D Curve - Lê Tấn Hùng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_do_hoa_hien_thuc_ao_bai_7_duong_cong_trong_khong_g.pdf
