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

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)