Page 1
CNTT-DHBK Hanoi hunglt@it-hut.edu.vn Đường cong - Curve Đường cong trong không gian 3D CURVE z Why use curves? Quỹ đạo chuyển động của 1 điểm trong không gian z Đ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. z Biểu diễn Điểm và kiểm soát đường cong -Points represent-and 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 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 2 Design (CAGD). 1 Khoa CNTT DHBK Hanoi Khoa CNTT DHBK Hanoi Phân loại Polynomial Parametric Curves z Trên cơ sở ràng buộc giữa điểm và đường trong cả ứng dụng khoa z What degree should we use to represent a học và thiết kế ta co thể phân làm 2 loại: curve? z Nội suy-Interpolation - đường cong đi qua các điểm, trong ứng We choose the third degree: 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ư z Cubic polynomials sai số phóng đại hay độ nhấp nhô của đường cong do đa thức bậc – Higher degrees: cao tạo nên. z Require more computation z Trong thiết kế nôi suy là cần thiết với các đối tượng nhưng không z Have extra “wiggles” phù hợp với các đối tượng có hình dáng bất kỳ "free form“. z Provide more flexibility than is required. z Xấp xỉ-Approximation - đường cong không cần đi qua các điểm,với z Are often used to model cars and aeroplanes 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. 3 Khoa CNTT DHBK Hanoi 4 Khoa CNTT DHBK Hanoi Tính chất cả đường cong bậc 3 Đường cong đa thức bậc ba z Tham biến – parametric sử dụng tham biến ngoài để biểu diễn cho z Phải đảm bảo là đường cong không gian với 3 trục toạ các tham biến trong độ x, y, z z Độ 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 z tránh được những tính toán phức tạp và những phần các điểm kiểm soát-control point. Với B-splines tính liên tục trên đạo nhấp nhô ngoài ý muốn xuất hiện ở những đường đa hàm bậc 2 second derivative hay độ cong được đảm bảo curvature. thức bậc cao z Độ 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 z Why cubic? hạn chế -oscillate. lower-degree polynomials give too little flexibility in controlling the – z Ví dụ Bézier curve, for instance, lies within the convex hull (polygon shape of the curve envelope) of the set of control points. – higher-degree polynomials can introduce unwanted wiggles and z Điêm kiểm soát cục bộ-local control. đường cong bị ảnh hưởng 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. – lowest degree that allows specification of endpoints and their derivatives – lowest degree that is not planar in 3D 5 Khoa CNTT DHBK Hanoi 6 Khoa CNTT DHBK Hanoi goupee.com fb.com/groups/goupee 1
Page 2
CNTT-DHBK Hanoi hunglt@it-hut.edu.vn Đường cong bậc 3 z Kinds of continuity: z Theo Lagrange: – G0: two curve segments join together z x = a + b u + c u2 + d u3 1 1 1 1 G1: directions of tangents are equal at the joint z y = a + b u + c u2 + d u3 – 2 2 2 2 z z = a + b u + c u2 + d u3 C1: directions and magnitudes of tangents are equal 3 3 3 3 – 3 phương trinh với 12 ẩn số z at the joint Với 3 điểm P0, P1, P2, P3 phương trình xác định z – Cn: directions and magnitudes of n-th derivative are equal at the joint P'1 p3 P1 p2 P'0 P1 P0 P0 7 Khoa CNTT DHBK Hanoi 8 Khoa CNTT DHBK Hanoi Đường cong Hermite z 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 z đường bậc ba sẽ xác định bởi hai điểm đầu và cuối cùng với hai góc z Thay vào: nghiêng tại hai điểm đó z p = p(u) = p (1-3u2+2u3) + p (3u2-2u3) z p = p(u) = k + k u + k u2 + k u3 0 1 0 1 2 3 + p ’(u-2u2+u3) + p ’(-u2+u3) z p(u) = ∑kiui i∈n 0 1 z p’ = p(u) = k + 2k u + 3k u2 1 2 3 ⎡ 1 0 0 0 ⎤ ⎡ p ⎤ ⎢ 0 ⎥ z p và p ta có hai độ dốc p ’ và p ’ với u = 0 và u = 1 tại hai điểm đầu ⎢ 0 0 1 0 ⎥ p 0 1 0 1 ⎢ ⎥ ⎢ ⎥ cuối của đoạn [0,1]. p = p(u) = [ 1 u u2 u3 ] . 1 z k + 2k + 3k = p ’ ⎢−3 3 −2 −1⎥ ⎢p' ⎥ 1 2 3 1 ⎢ ⎥ ⎢ 0 ⎥ z k = p k = p ’ 2 2 1 1 p' 0 0 1 1 ⎣ ⎦ ⎣ ⎦ z k = 3(p – p ) - 2p ’ – p ’ 1 2 1 0 0 1 9 z k = 2(p -p ) + p ’ + p ’ 10 3 0 1 0 1 Khoa CNTT DHBK Hanoi Khoa CNTT DHBK Hanoi Đường cong Bezier z 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) z 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). z Paul Bezier, RENAULT, 1970 đường và bề mặt UNISURF 11 Khoa CNTT DHBK Hanoi 12 Khoa CNTT DHBK Hanoi goupee.com fb.com/groups/goupee 2
Page 3
CNTT-DHBK Hanoi hunglt@it-hut.edu.vn z po, p tương đương với p , p trên đường Hermite. 3 0 1 diểm trung gian p , p được xác định bằng 1/3 theo 1 2 độ dài của vector tiếp tuyến tại điểm po và p 3 z p ’ = 3(p – p ) 0 1 0 ⎡ 1 0 0 0 ⎤ ⎡p ⎤ p ’ = 3(p – p ) ⎢ 0 ⎥ z ⎢−3 3 0 0 ⎥ p 3 3 2 p = p(u) = [ 1 u u2 u3 ] ⎢ ⎥ ⎢ ⎥ 1 z p = p(u) = p (1-3u2+2u3) + p (3u2-2u3) + p ’(u- ⎢ 3 −6 3 0 ⎥ ⎢p ⎥ 0 1 0 2 2u2+u3) + p ’(-u2 + u3) ⎢−1 3 −3 1 ⎥ ⎢p ⎥ 1 ⎣ ⎦ ⎣ ⎦ p = p(u) = p (1 - 3u + 3u - u ) + p (3u-6u 3u ) 3 z 2 3 2+ 3 0 1 + p (3u2 - 3u3) + p u3 2 3 13 Khoa CNTT DHBK Hanoi 14 Khoa CNTT DHBK Hanoi Ưu điểm De Casteljau algorithm z 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 ’ và p ’ của Hermite. 0 1 z Nằm trong đa giác kiểm soát với số điểm trung gian tuỳ ý( số bậc tuỳ ý) z đ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 đó 15 Khoa CNTT DHBK Hanoi 16 Khoa CNTT DHBK Hanoi Biểu thức Bezier-Bernstain Tính chất z Tổng quát hoá với n +1 điểm kiểm soát z P0 và Pn nằm trên đường cong. n z Đường cong liên tục và có đạo hàm liên tục tất cả các p(u) = ∑B (u)p bậc i,n i i=0 Tiếp tuyến của đường cong tại điểm P0 là đường P0P1 z ∑n p′(u) = n B (u)(p − P) và tại Pn là đường Pn-1Pn . i,n−1 i+1 i i=0 z Đường cong nằm trong đường bao lồi convex hull của B (u) = C(n,i)ui(1−u)n−i các điểm kiểm soát. i,n z This is because each successive Pi(j) is a convex n! combination of the points Pi(j-1) and Pi-1(j-1) . C(n,i) = p ... pn : vector vi!(nị−trí ci)! ủa đa giác n+1 đỉnh z P1 ,P2 , … ,Pn-1 nằm trên đường cong khi và chỉ khi z 0 đường cong là đoạn thẳng. 17 Khoa CNTT DHBK Hanoi 18 Khoa CNTT DHBK Hanoi goupee.com fb.com/groups/goupee 3
Page 4
CNTT-DHBK Hanoi hunglt@it-hut.edu.vn Review: Bézier Curve Prop’s [1/6] Đường bậc ba Spline z We looked at some properties of Bézier curves. z Spline đi qua n điểm cho trước mà mỗi đoạn là z Generally “Good” Properties đường bậc ba độc lập có độ dốc và độ cong liên – Endpoint Interpolation tục tại mỗi điểm kiểm soát hay điểm nút – Smooth Joining Với n điểm:n-1 đoạn với mỗi đoạn 4 vector hệ số Affine Invariance z – Convex-Hull Property 4(n-1) cho n-1 đoạn, và 2(n-1) điều kiện biên và n- – z Generally “Bad” Properties 2 điều kiện về độ dốc cùng n-2 về độ cong – Not Interpolating z Spline dùng để chỉ phương pháp biểu diễn – 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 19 Khoa CNTT DHBK Hanoi 20 Khoa CNTT DHBK Hanoi y Pn-1’ Đường cong bậc ba Spline Pn-1 z u = 0 với : (u ... un ) uj > uj Po’ P1 0 0 -1 +1 x z P z ui = ui + di o +1 +1 z C để không có sự gián đoạn giữa hai đoạn cong. 0 C tính liên tục bậc nhất hay đạo hàm bậc nhất tại điểm ⎡ 1 0 0 0 ⎤ ⎡ p ⎤ z 1 ⎢ ⎥ ⎢ 0 ⎥ nối. p = [ 1 u u2 u3 ] ⎢ 0 0 1 0 ⎥ ⎢ p ⎥ . 1 C đạo hàm bậc hai liên tục của đường cong tại điểm nối ⎢−3 3 −2 −1⎥ ⎢p' ⎥ z 2 ⎢ ⎥ ⎢ 0 ⎥ ⎣ 2 2 1 1 ⎦ ⎣p' ⎦ 1 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 (ui =1) là đạo hàm bậc hai -1 -1 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)= P’’i(0) -1 21 Khoa CNTT DHBK Hanoi 22 Khoa CNTT DHBK Hanoi B-Splines: Đường cong B-spline The Idea [1/2] Đường cong B-spline là đường cong được sinh z The repeated-lirping idea that produced the Bézier z curves has the drawbacks that is produces polynomials ra từ đa giác kiểm soát mà bậc của nó không phụ with high degree that are nonzero almost everywhere. thuộc vào số đỉnh của đa giác kiểm soát. 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. 23 Khoa CNTT DHBK Hanoi 24 Khoa CNTT DHBK Hanoi goupee.com fb.com/groups/goupee 4
Page 5
CNTT-DHBK Hanoi hunglt@it-hut.edu.vn B-Splines: The Idea [2/2] B-Splines z We form an order-2 B-Spline by lirping between the order-1 blending functions. Types of B-Splines Approximation Curves Used – 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. B-Spline approximations can be classified based on the – So each blending function is defined in pieces. Each piece is a spacing of the knot vector and the use of weights. polynomial of degree 1 (graph is a line). – So an order-2 B-spline is just the control polygon. 1. Uniform/Periodic B-splines : The spacing is – Again, any number of control points may be used. unform and the knots (control points) are equispaced e.g. We form an order-3 B-Spline by lirping between the order-2 blending [0,1,2,3,4,5] These have satisfactory smoothness but lack z local control and the starting and ending poits are ill functions. defined as above. – Now blending functions are smooth. They start at 0, curve up to 1 then 2. Non-periodic: The knots are repeated at the ends m back down. Again, each function is 0 most of the time. times and the interior is equispaced. e.g. [0 0 0 1 2 3 3 3 – Again, each blending function is defined in pieces. Each piece is a ] These can be used to force the control point to start polynomial of degree 2. and finish at a control point. 3. Non-uniform B-Splines : The spacing is non- z 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 higher order. ] These can be used to obtain local control 25 – See the blue book for details and graphs. Khoa CNTT DHBK Hanoi 26 Khoa CNTT DHBK Hanoi B-spline ∑n ⎧1 u∈[u ,u ] P(u) = N (u).P N (u) = ⎨ i i+1 i,k i i,1 0 others i=0 ⎩ (u −U ) (U −u) N (u) = i+1−k N (u) + i+1 N (u) i,k U −U i−1,k−1 (U −U ) i,k−1 i i+1−k i+1 i+2−k 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 27 U=[U1,U2...Un+k+1] Khoa CNTT DHBK Hanoi 28 Khoa CNTT DHBK Hanoi Đặc điểm B Spline - Đều và tuần hoàn 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 Vecto nút là đều khi giá trị của chúng cách đều nhau một z B-spline có thể được tạo qua hai điểm đầu, cuối và tiếp xúc với vector khoảng ∇ xác định. Trong các bài toán thực tế, vecto nút đầ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í đều được bắt đầu từ 0 và tăng 1 cho đến giá trị lớn nhất 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 Ví dụ: [ 0 1 2 3 4 5 ] với ∇ xác định = 1 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 z [ -2 -1/2 1 5/2 4 ] với ∇ xác định = 3/2 mãn. ∑n z Với cấp là k, số điểm kiểm soát là n+1 thì vecto nút đều là z Số lượng các nút, bậc cNủa đư(u)ờ=ng cong v1 à số điểm điều khiển luôn có i,k U=[0 1 2 ...n+k] khoảng tham số (k-1)≤u≤(n+1). các quan hệ ràng buội=c:0 z z 0 ≤ u ≤ n - k + 2 z Khi vecto nút là đều thì ta có Ni,k(u)=Ni-1,k(u- 1)=Ni+1,k(u+1) 29 Khoa CNTT DHBK Hanoi 30 Khoa CNTT DHBK Hanoi goupee.com fb.com/groups/goupee 5
Page 6
CNTT-DHBK Hanoi hunglt@it-hut.edu.vn Không tuần hoàn Open – Non Uniform z Một vector không tuần hoàn hoặc mở Cấp số lượng nút (m Vector nút là vector nút có giá trị nút tại các điểm k = n + k) không tuần đầu cuối lặp lại với số lượng các giá trị hoàn lặp lại này bằng chính cấp k của 2 6 [0 0 1 2 3 3] đường cong và các giá trị nút trong mỗi điểm lặp này là bằng nhau 3 7 [0 0 0 1 2 2 2] 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. 4 8 [0 0 0 0 1 1 1 1] 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 31 Khoa CNTT DHBK Hanoi 32 Khoa CNTT DHBK Hanoi B-Splines: Properties Kết luận z The most used B-splines are: z B-spline là một dòng của Bezier – Order 3 (“quadratic B-splines”). z Smooth. 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 – Order 4 (“cubic B-splines”). thành Bezier z Smoother, but control is a little less local. 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 z B-splines have the following properties. rõ ràng hơn. – An order-k B-spline has blending functions that are defined in pieces, z Khi tồn tại anh hưởng cục bộ càng lớn và đường cong phai đi qua điểm 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. ☺ z Chúng ta có thể thay đổi hình dạng đường cong B-spline bằng cách: – B-splines are affine invariant (of course). z Thay đổi kiểu vecto nút : đều tuần hoàn, mở, không đều – They have the convex-hull property. ☺ Thay đổi cấp k của đường cong z – They have local control. ☺ A B-spline (of order 3 or more) does not interpolate any of its control z Thay đổi số đỉnh và vị trí các đỉnh đa giác kiểm soát – points. / But we can deal with this … z Sử dụng các điểm kiểm soát trùng nhau 33 Khoa CNTT DHBK Hanoi 34 Khoa CNTT DHBK Hanoi Other Splines: Non-uniform Rational B-Splines(NURBS) NURBS, etc. z There are any number of other types of splines. The last 3 types are good for representing free form curves but also introduce – Often we want a very general type of curve that will do whatever we want. unnecessary approximations in the representation of conic sections. NURBS build on non-uniform B-Splines and introduce a weight function to obtain an approximation z One such type of curve that has been very successful is the NURBS. that retains all the advantages of the non-uniform B-Splines and is also capable of – NURBS = Non-Uniform Rational B-Spline. exact representation of conic sections (circles, parabolas etc.).The general form is – A NURBS is defined using rational functions. given below: 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 The curve is described as rational since it is expressed as the ratio of two from the viewer’s eye, through the pixel, and we see where the ray came from. polynomials. w defines a weight function. If w is set to 1 we get back the non- – In order to do ray tracing efficiently, we must be able to test quickly whether a i i particular ray hits a particular object and, if so, where. uniform B-Spline. Other values of the w can be used to produce curves for straight i – Types of surfaces in which this test can be done quickly will be more useful in 3-D line, parabola, ellipse and hyperbola. graphics. 35 Khoa CNTT DHBK Hanoi 36 Khoa CNTT DHBK Hanoi goupee.com fb.com/groups/goupee 6
Affichage des 6 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !