CNTT-DHBK Hanoi

1
(c) SE/FIT/HUT 2002
Đường cong trong không gian
3D CURVE
(c) SE/FIT/HUT 2002
2
Đường cong - Curve

Why use curves? Quỹ đạo chuyển động của 1 điểm trong
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
3
Phân loại

Trên cơ sở ràng buộc giữa điểm và đường trong cảứng dụng khoa học và
thiết kế ta co thể phân làm 2 loại:

Xấp xỉ-Approximation -

Được ứng dụng trong mô hình hoá hình học


Nội suy-Interpolation

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“.
(c) SE/FIT/HUT 2002
4
Biểu diễn Đường cong

Tường minh y=f(x)

y = f(x), z = g(x)

impossible to get multiple values for a single
x
• break curves like circles and ellipses
into segments

not invariant with rotation
• rotation might require further segment
breaking

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
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
5
Đường cong tham biến

Biểu diễn các đường cong tham biến
Parametric representation:

x = x(t), y = y(t), z = z(t)

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

Define a parameter space

1D for curves

2D for surfaces

Define a mapping from parameter space to 3D points


A function that takes parameter values and gives back 3D points

The result is a parametric curve or surface
0
t
1
Mapping F :t → (x, y, z)
(c) SE/FIT/HUT 2002
6
Parametric Curves

We have seen the parametric form for a line:

Note that x, y and z are each given by an equation that
involves:

The parameter t

Some user specified control points, x
0
and x
1

This is an example of a parametric curve
10
10
10
)1(
)1(
)1(

zttzz
yttyy
xttxx
−+=
−+=
−+
=
CNTT-DHBK Hanoi

2
(c) SE/FIT/HUT 2002
7
Đường cong đa thức bậc ba

Phải đảmbảolàđường cong không gian với 3 trụctoạđộx, y, z

tránh đượcnhững tính toán phứctạpvànhững phầnnhấp nhô ngoài ý
muốnxuấthiện ở những đường đathứcbậc cao

Why cubic?
(c) SE/FIT/HUT 2002
8
P0
P1
p2
p3
P0
P'0
P1
P'1

Đ
ường cong bậc 3

x = a
1
+ b
1
u + c
1
u
2
+ d
1
u
3

y = a
2
+ b
2
u + c
2
u
2
+ d
2
u
3

z = a

3
+ b
3
u + c
3
u
2
+ d
3
u
3

Với 3 điểm P0, P1, P2, P3 phương trình
xác định
(c) SE/FIT/HUT 2002
9
Hermite Spline

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 draw smooth curves

The control points are adjusted by the user to control the shape of the curve

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:


The endpoints of the curve

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
10
Đường cong Hermite

p = p(u) = k
0
+ k
1
u + k
2
u
2
+ k
3
u
3

p(u) = ∑kiui i∈n

p
0
và p
1

ta có hai độ dốc p
0
’vàp
1
’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 curve must pass through p
0
when u=0

The derivative must be p’
0
when u=0

The curve must pass through p
1
when u=1

The derivative must be p’
1
when u=1
(c) SE/FIT/HUT 2002
11
Basis Functions

A point on a Hermite curve is obtained by multiplying each control point
by some function and summing


The functions are called basis functions
(c) SE/FIT/HUT 2002
12

Thay vào:

p = p(u) = p
0
(1-3u
2
+2u
3
) + p
1
(3u
2
-2u
3
)
+ p
0
’(u-2u
2
+u
3
) + p
1
’(-u
2

+u
3
)
p = p(u) = [ 1 u u
2
u
3
]
CNTT-DHBK Hanoi

3
(c) SE/FIT/HUT 2002
13
Đường cong Bezier

Sử dụng điểm và các vector kiểmsoátđược độ dốccủa đường
cong tạinhưng điểmmànóđiqua.(Hermit)

không đượcthuậnlợi cho việcthiếtkế tương tác, không tiếpcận
vào các độ dốccủa đường cong bằng các giá trị số (Hermite).

Paul Bezier, RENAULT, 1970 đường và bề mặt UNISURF
(c) SE/FIT/HUT 2002
14

po, p
3
tương đương với p
0
, p

1
trên đường Hermite. diểm trung
gian p
1
, p
2
được xác định bằng 1/3 theo độ dài của vector tiếp
tuyến tại điểm po và p
3

p
0
’= 3(p
1
–p
0
)

p
3
’= 3(p
3
–p
2
)

p = p(u) = p
0
(1-3u2+2u3) + p
1

(3u2-2u3) + p
0
’(u-2u
2
+u
3
) + p
1
’(-
u
2
+ u
3
)

p = p(u) = p
0
(1 - 3u + 3u
2
-u
3
) + p
1
(3u-6u
2
-3u
3
)
+ p
2

(3u
2
-3u
3
) + p
3
u
3
(c) SE/FIT/HUT 2002
15
Biểu diễn Ma trận
p = p(u) = [ 1 u u
2
u
3
]

























−−
−
−
3
2
1
0
1331
0363
0033
0001
p
p
p
p
0
0.2
0.4
0.6
0.8

1
1.2
B0
B1
B2
B3
(c) SE/FIT/HUT 2002
16
Ưu điểm

dễ dàng kiểm soát hi`nh dạng của đường cong hơn vector tiếp
tuyến tại p
0
’vàp
1
’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 đó
(c) SE/FIT/HUT 2002
17
Example
Bezier Curves

[UW]
(c) SE/FIT/HUT 2002
18

Sub-Dividing Bezier Curves
P
0
P
1
P
2
P
3
M
01
M
12
M
23
M
012
M
123
M
0123
CNTT-DHBK Hanoi

4
(c) SE/FIT/HUT 2002
19
Sub-Dividing Bezier Curves
P
0
P

1
P
2
P
3
(c) SE/FIT/HUT 2002
20
Sub-Dividing Bezier Curves

Step 1: Find the midpoints of the lines joining the original control vertices.
Call them M
01
, M
12
, M
23

Step 2: Find the midpoints of the lines joining M
01
, M
12
and M
12
, M
23
. Call
them M
012
, M
123


Step 3: Find the midpoint of the line joining M
012
, M
123
. Call it M
0123

The curve with control points P
0
, M
01
, M
012
and M
0123
exactly follows the
original curve from the point with t=0 to the point with t=0.5

The curve with control points M
0123
, M
123
, M
23
and P
3
exactly follows the
original curve from the point with t=0.5 to the point with t=1
(c) SE/FIT/HUT 2002

21
de Casteljau’s Algorithm

You can find the point on a Bezier curve for any parameter value t with a similar
algorithm

Say you want t=0.25, instead of taking midpoints take points 0.25 of the way
P
0
P
1
P
2
P
3
M
01
M
12
M
23
t=0.25
(c) SE/FIT/HUT 2002
22
BiểuthứcBezier-Bernstain

Tổng quát hoá vớin+1 điểmkiểm soát

p
0

... pn : vector vị trí của đagiácn+1 đỉnh
))(()(
)()(
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) SE/FIT/HUT 2002
23
Tính chất

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.

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
24
Review:

Bézier Curve Prop’s [1/6]

We looked at some properties of Bézier curves.

Generally “Good” Properties

Endpoint Interpolation

Smooth Joining

Affine Invariance

Convex-Hull Property

Generally “Bad” Properties

Not Interpolating

No Local Control
CNTT-DHBK Hanoi

5
(c) SE/FIT/HUT 2002
25
Problem with Bezier Curves

To make a long continuous curve with Bezier segments
requires using many segments

Maintaining continuity requires constraints on the control

point positions

The user cannot arbitrarily move control vertices and automatically
maintain continuity

The constraints must be explicitly maintained

It is not intuitive to have control points that are not free
(c) SE/FIT/HUT 2002
26
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

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
study are translation and rotation invariant

Some forms of curves, rational splines, are also perspective invariant

Can do perspective transform of control points and then evaluate the curve
(c) SE/FIT/HUT 2002
27
Longer Curves


A single cubic Bezier or Hermite curve can only capture a small class of curves

At most 2 inflection points

One solution is to raise the degree

Allows more control, at the expense of more control points and higher degree
polynomials

Control is not local, one control point influences entire curve

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
(c) SE/FIT/HUT 2002
28
Piecewise Bezier Curve
“knot”
P
0,0
P
0,1
P
0,2
P

0,3
P
1,0
P
1,1
P
1,2
P
1,3
(c) SE/FIT/HUT 2002
29
Continuity

When two curves are joined, we typically want some degree of continuity
across the boundary (the knot)

C
0
, “C-zero”, point-wise continuous, curves share the same point where they
join

C
1
, “C-one”, continuous derivatives, curves share the same parametric
derivatives where they join

C
2
, “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 C
1
across a
knot?

Question: How do we ensure that two Bezier curves are C
0
, or C
1
, or C
2
across a knot?
(c) SE/FIT/HUT 2002
30
Đườ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