Bài giảng môn Đồ họa và hiện thực ảo - Bài 7: Đường cong trong không gian

CNTT-DHBK Hanoi hunglt@it-hut.edu.vn

Đường cong - Curve

Đường cong trong không gian 3D CURVE

(cid:122) Why use curves? Quỹ đạo chuyển động của 1 điểm trong không gian (cid:122) Điểm biểu diễn Đường cong -curve represents points:

– là phương pháp được sử dụng trong khoa học vật lý và kỹ nghệ nói

chung.

– Các điểm dữ liệu được đo chính xác trên các thực thể sẽ chính đối

tượng cơ sở. Đường cong đi qua các điểm dữ liệu hiển thị hỗ trợ cho việc nhận ra xu hướng và ý nghĩa cả các điểm dữ liệu.

– Các kỹ thuật phức tạp “vd bình phương sai số” được dùng đưa đường

cong hợp với 1 dạng toán học cơ bản.

(cid:122) Biểu diễn Điểm và kiểm soát đường cong -Points represent-and

thiết kế và các điểm đóng vai trò là công cụ để kiểm soát và và mô hình hoá đường cong.

– Cách tiếp cận này là cơ sở của lĩnh vực Computer Aided Geometric

Design (CAGD).

Khoa CNTT DHBK Hanoi

control-the curve. – đường cong là các đối tượng cơ bản thường là kết quả của tiến trình

2 1

Phân loại

Polynomial Parametric Curves

(cid:122) Trên cơ sở ràng buộc giữa điểm và đường trong cả ứng dụng khoa

(cid:122) What degree should we use to represent a

(cid:122) Nội suy-Interpolation - đường cong đi qua các điểm, trong ứng

curve? – We choose the third degree:

(cid:122) Cubic polynomials

– Higher degrees:

học và thiết kế ta co thể phân làm 2 loại:

(cid:122) Trong thiết kế nôi suy là cần thiết với các đối tượng nhưng không

dụng khoa học các yêu cầu về ràng buộc sử dụng đa thức hay các hàm bậc cao tuy nhiên kết quả thường có những hiệu ứng phụ như sai số phóng đại hay độ nhấp nhô của đường cong do đa thức bậc cao tạo nên.

(cid:122) Require more computation (cid:122) Have extra “wiggles” (cid:122) Provide more flexibility than is required. (cid:122) Are often used to model cars and aeroplanes

(cid:122) Xấp xỉ-Approximation - đường cong không cần đi qua các điểm,với các ứng dụng khoa học ta gọi là trung bình dữ liệu- data averaging hay trong thiết kế điểu khiển đường cong.

Khoa CNTT DHBK Hanoi

phù hợp với các đối tượng có hình dáng bất kỳ "free form“.

4 3

Tính chất cả đường cong bậc 3

Đường cong đa thức bậc ba

(cid:122) Tham biến – parametric sử dụng tham biến ngoài để biểu diễn cho

(cid:122) Phải đảm bảo là đường cong không gian với 3 trục toạ

độ x, y, z

(cid:122) Độ mượt - smooth. Với đường cong Hermite and Bézier tính liên

(cid:122) tránh được những tính toán phức tạp và những phần nhấp nhô ngoài ý muốn xuất hiện ở những đường đa thức bậc cao

(cid:122) Why cubic?

các tham biến trong

– lower-degree polynomials give too little flexibility in controlling the

(cid:122) Ví dụ Bézier curve, for instance, lies within the convex hull (polygon

– higher-degree polynomials can introduce unwanted wiggles and

(cid:122) Điêm kiểm soát cục bộ-local control. đường cong bị ảnh hưởng

– lowest degree that allows specification of endpoints and their

– lowest degree that is not planar in 3D

Khoa CNTT DHBK Hanoi

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. (cid:122) Độ 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. shape of the curve envelope) of the set of control points. require more computation mạnh nhất với chính các điểm kiểm soát gần chúng nhất. derivatives 6 5

1

CNTT-DHBK Hanoi hunglt@it-hut.edu.vn

Đường cong bậc 3

(cid:122) Kinds of continuity:

– G0: two curve segments join together – G1: directions of tangents are equal at the joint – C1: directions and magnitudes of tangents are equal

at the joint

(cid:122) Theo Lagrange: (cid:122) x = a1 + b1u + c1u2 + d1u3 (cid:122) y = a2 + b2u + c2u2 + d2u3 (cid:122) z = a3 + b3u + c3u2 + d3u3 (cid:122) 3 phương trinh với 12 ẩn số (cid:122) Với 3 điểm P0, P1, P2, P3 phương trình xác định

– Cn: directions and magnitudes of n-th derivative are

P'1

equal at the joint

p3

p2

P1

P'0

P1

P0

Khoa CNTT DHBK Hanoi

Đường cong Hermite

(cid:122) Phương pháp Hermite dựa trên cơ sở của cách biểu diễn

7 8

(cid:122) đường bậc ba sẽ xác định bởi hai điểm đầu và cuối cùng với hai góc

Ferguson hay Coons năm 60

(cid:122) Thay vào: (cid:122) p = p(u) = p0(1-3u2+2u3) + p1(3u2-2u3) + p0’(u-2u2+u3) + p1’(-u2+u3)

nghiêng tại hai điểm đó

(cid:122) p = p(u) = k0 + k1u + k2u2 + k3u3 (cid:122) p(u) = ∑kiui (cid:122) p’ = p(u) = k1 + 2k2u + 3k3u2

001

(cid:122) p0 và p1 ta có hai độ dốc p0’ và p1’ với u = 0 và u = 1 tại hai điểm đầu

100

i∈n

33 2 − − 122

p p

1 ' '

⎡ ⎢ ⎢ p = p(u) = [ 1 u u2 u3 ] ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎥ 1 − ⎥ 1 ⎦

⎤ ⎥ ⎥ ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎢ ⎢ ⎣

k1 = p1’

Khoa CNTT DHBK Hanoi

Đường cong Bezier

(cid:122) 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)

(cid:122) 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).

(cid:122) Paul Bezier, RENAULT, 1970 đường và bề mặt

UNISURF

Khoa CNTT DHBK Hanoi

cuối của đoạn [0,1]. (cid:122) k1 + 2k2 + 3k3 = p1’ (cid:122) k0 = p0 (cid:122) k2 = 3(p1 – p0) - 2p0’ – p1’ (cid:122) k3 = 2(p0-p1) + p0’ + p1’ 9 10

11 12

2

CNTT-DHBK Hanoi hunglt@it-hut.edu.vn

(cid:122) 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

p = p(u) = [ 1 u u2 u3 ]

0 36

33 − 3

0 0

(cid:122) p0’ = 3(p1 – p0) (cid:122) p3’ = 3(p3 – p2) (cid:122) p = p(u) = p0(1-3u2+2u3) + p1(3u2-2u3) + p0’(u-

2u2+u3) + p1’(-u2 + u3)

− 31

−

p 0 p 1 p p 3

⎡ ⎢ ⎢ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎢ ⎢ ⎣

(cid:122) p = p(u) = p0(1 - 3u + 3u2 - u3) + p1(3u-6u2+3u3)

+ p2(3u2 - 3u3) + p3u3

Khoa CNTT DHBK Hanoi

13 14

Ưu điểm

De Casteljau algorithm

(cid:122) dễ dàng kiểm soát hi`nh dạng của đường cong hơn

vector tiếp tuyến tại p0’ và p1’ của Hermite.

(cid:122) Nằm trong đa giác kiểm soát với số điểm trung gian

tuỳ ý( số bậc tuỳ ý)

(cid:122) đ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 đó

Khoa CNTT DHBK Hanoi

15 16

Tính chất

Biểu thức Bezier-Bernstain

(cid:122) Tổng quát hoá với n +1 điểm kiểm soát

(cid:122) P0 và Pn nằm trên đường cong. (cid:122) Đường cong liên tục và có đạo hàm liên tục tất cả các

up )(

puB )( i

ni ,

bậc

∑

(cid:122) Tiếp tuyến của đường cong tại điểm P0 là đường P0P1

và tại Pn là đường Pn-1Pn .

′ )( up

(

)

−

ni ,

pu )( i

P i

1 −

1 +

∑

(cid:122) Đường cong nằm trong đường bao lồi convex hull của

in −

các điểm kiểm soát.

),( uinC

)

−

)(, uB ni

(cid:122) This is because each successive Pi(j) is a convex combination of the points Pi(j-1) and Pi-1(j-1) .

)i,n(C

!n − )!in(!i

(cid:122) P1 ,P2 , … ,Pn-1 nằm trên đường cong khi và chỉ khi

(cid:122) p0 ... pn : vector vị trí của đa giác n+1 đỉnh

đường cong là đoạn thẳng.

Khoa CNTT DHBK Hanoi

17 18

3

CNTT-DHBK Hanoi hunglt@it-hut.edu.vn

Review: Bézier Curve Prop’s [1/6]

Đường bậc ba Spline

(cid:122) We looked at some properties of Bézier curves. (cid:122) Generally “Good” Properties

(cid:122) 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

– Endpoint Interpolation – Smooth Joining – Affine Invariance – Convex-Hull Property

(cid:122) Generally “Bad” Properties

(cid:122) 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 (cid:122) Spline dùng để chỉ phương pháp biểu diễn

– Not Interpolating – No Local Control

đườ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 Hanoi

’

Pn-1

Đường cong bậc ba Spline

’

z Po

(cid:122) u0 = 0 với : (u0 ... un-1) uj+1 > uj (cid:122) ui+1 = ui + di+1 (cid:122) C0 để không có sự gián đoạn giữa hai đoạn cong. (cid:122) C1 tính liên tục bậc nhất hay đạo hàm bậc nhất tại điểm

p = [ 1 u u2 u3 ]

nối.

p p 1 p '

(cid:122) C2 đạo hàm bậc hai liên tục của đường cong tại điểm nối

001 100 33 2 − − 122

⎡ ⎢ ⎢ ⎢ ⎢ ⎣

0 ⎤ ⎥ 0 ⎥ ⎥ 1 − ⎥ 1 ⎦

⎤ ⎥ ⎥ ⎥ ⎥ ⎦

19 20

⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (cid:122) 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.

(cid:122) P’’i-1(1)= P’’i(0)

Khoa CNTT DHBK Hanoi

21 22

B-Splines: The Idea [1/2]

Đường cong B-spline

(cid:122) The repeated-lirping idea that produced the Bézier

(cid:122) Đườ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.

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.

(cid:122) 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.

(cid:122) Now we make higher-order B-splines using a repeated-

lirping procedure. – But this time, we can use any number of control points.

Khoa CNTT DHBK Hanoi

23 24

4

CNTT-DHBK Hanoi hunglt@it-hut.edu.vn

B-Splines

B-Splines: The Idea [2/2]

(cid:122) We form an order-2 B-Spline by lirping between the order-1 blending

Types of B-Splines Approximation Curves Used

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

B-Spline approximations can be classified based on the spacing of the knot vector and the use of weights.

polynomial of degree 1 (graph is a line).

functions. – As discussed, we get functions that start at 0, ramp up to 1 and back

1. Uniform/Periodic B-splines : The spacing is

– So an order-2 B-spline is just the control polygon. – Again, any number of control points may be used.

(cid:122) We form an order-3 B-Spline by lirping between the order-2 blending

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

back down. Again, each function is 0 most of the time.

– Again, each blending function is defined in pieces. Each piece is a

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.

polynomial of degree 2.

functions. – Now blending functions are smooth. They start at 0, curve up to 1 then

3. Non-uniform B-Splines : The spacing is non-

(cid:122) We continue this repeated-lirping procedure to define B-splines of

uniform and or repeated knots e.g. [0 1 1 2 4 5 6 6 ] These can be used to obtain local control

Khoa CNTT DHBK Hanoi

higher order. – See the blue book for details and graphs. 25 26

B-spline

[

]

∈

, uu i i

1 +

)( uP

( PuN i

ki ,

)( uN 1, i

∑

others

1 ⎧ ⎨ 0 ⎩

)

1 −+

u )(

uN )( ki ,

ki ,

−

1 −

U ( U (

)

− 1 i + U −

Uu ( − i UU − i

1 −+

1 +

2 −+

(cid:122) Ni,k(u) đa thức B-Spline cơ bản (cid:122) Với n+ 1 sô điểm kiểm soát (cid:122) Pi điểm kiểm soát thứ i (cid:122) k bậc của đường cong 1

của

đường

cong

Khoa CNTT DHBK Hanoi

nút vector U=[U1,U2...Un+k+1]

B Spline - Đều và tuần hoàn

27 28

Đặc điểm

(cid:122) B-spline không đi qua hai điểm đầu và cuối trừ khi hàm hợp được

(cid:122) 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

(cid:122) 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.

(cid:122) Ví dụ: [ 0 1 2 3 4 5 ] với ∇ xác định = 1 (cid:122) [ -2 -1/2 1 5/2 4 ] với ∇ xác định = 3/2

(cid:122) 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

dùng là tuyến tính.

(u)

1 (cid:122) Số lượng các nút, bậc của đường cong và số điểm điều khiển luôn có

ki,

0i =

∑ các quan hệ ràng buộc:

(cid:122)

mãn.

(cid:122) Với cấp là k, số điểm kiểm soát là n+1 thì vecto nút đều là (cid:122) U=[0 1 2 ...n+k] khoảng tham số (k-1)≤u≤(n+1). (cid:122) Khi vecto nút là đều thì ta có Ni,k(u)=Ni-1,k(u-

1)=Ni+1,k(u+1)

Khoa CNTT DHBK Hanoi

0 ≤ u ≤ n - k + 2

29 30

5

CNTT-DHBK Hanoi hunglt@it-hut.edu.vn

Không tuần hoàn Open – Non Uniform

số lượng nút (m = n + k)

Cấp k

Vector nút không tuần hoàn

[0 0 1 2 3 3]

(cid:122) 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

[0 0 0 1 2 2 2]

(cid:122) 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.

[0 0 0 0 1 1 1 1]