Adjustment Algorithms for Bézier Curve and Surface Zhangxiang Ye, Xiang Long, Xiao-Ming Zeng Department of Mathematics, Xiamen University, Xiamen 361005, P. R. China. E-mail:
[email protected],
[email protected],
[email protected] Abstract—In this paper we construct a new kind of basis functions of Bézier curve with single shape parameter, and then by these basis functions we give a practical algorithm of curve modeling. We discuss some important properties of the basis functions and the corresponding curves. Further, we extend our study to the tensor product surface with two shape parameters. We construct the new basis functions of the surface and discuss the properties of these basis functions and the surface correspondingly. Index Terms—Algorithm; Bézier curve; shape parameter; basis functions; Bézier surface I. INTRODUCTION Bézier curves and surfaces are characterized by their control meshes, their shape can be modified only by moving their control points. But if don’t want to change the control meshes, the curve or the surface with shape parameters is a good choice. There have been a lot of researches on the curves and the surfaces with shape parameters. In [7] Wang and Wang presented Bézier basis with shape parameter by an integral approach. Han [5], [6] presented the trigonometric polynomial curve with shape parameter. In [8] Yang and Zeng gave a way to change the shape of curves with n shape parameters, and constructed the triangular surface with 3n(n+1)/2 shape parameters. In [2] Cheng and Zeng extended Bézier curves to polynomial of degree n+ 1, but the curves’ basis function is expressed as two categories via n is odd or even. Motivated by the work of Yang, Zeng [8] and Cheng, Zeng [2], in this paper we construct a kind of basis functions of curve with single shape parameter, and then by these basis functions we give a practical algorithm of curve modeling. We discuss some important properties of the basis functions and the corresponding curves, such as the properties of linear independence of the basis functions, unimodality of the basis functions, the endpoint properties of the curve, variation di- minishing of the curve and so on. We also show the change tendency of the curve with the change of shape parameter. By increase (or reduce) the shape parameter we can push curve towards (or pull away from) the control polygons intuitively. In the last section of the paper, we extend our study to the tensor surface with two shape parameters. We construct the new basis functions of these surfaces and discuss the properties of these basis functions and the surface correspondingly. II. CONSTRUCTION OF BASIS FUNCTIONS The original Bézier curve with control points Pi are defined by P (t) = n∑ i=0 Bi,n(t)Pi where Bi,n(t) = ( n i ) ti(1− t)n−i t ∈ [0, 1] is the Bernstein basis function of degree n. Definition 1: For n ≥ 2 t ∈ [0, 1] , we define the Bézier basis with shape parameter by B̃0,n(t) = B0,n(t)− λ 1 n+ 1 B1,n+1(t) B̃i,n(t) = Bi,n(t) + λ( n− 2i+ 1 n2 − 1 Bi,n+1(t) −n− 2i− 1 n2 − 1 Bi+1,n+1(t)) (1) B̃n,n(t) = Bn,n(t)− λ 1 n+ 1 Bn,n+1(t) where λ ∈ [−1, 1] is the shape parameter. We can rewrite (1) as: B̃i,n(t) = ( n+ 1− i n+ 1 + n− 2i+ 1 n2 − 1 λ)Bi,n+1(t) +( i+ 1 n+ 1 − n− 2i− 1 n2 − 1 λ)Bi+1,n+1(t) (2) Fig. 1 shows the Bézier basis with shape parameter of degree 4. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 λ = −1 λ = 0 λ = 1 Fig. 1. The quartic Bézier basis with shape parameter. λ = −1, 0, 1 978-1-4244-6005-2/10/$26.00 ©2010 IEEE The 5th International Conference on Computer Science & Education Hefei, China. August 24–27, 2010 1712 ThP13.3 III. PROPERTIES OF THE BASIS The new basis functions B̃i,n(t) hold following properties • Properties at the endpoints B̃i,n(0) = { 0 i �= 0 1 i = 0 B̃i,n(1) = { 0 i �= n 1 i = n (3) B̃ (j) i,n(0) = 0, j = 0, 1, . . . , i− 1; B̃ (k) i,n (1) = 0, k = 0, 1, . . . , n− i− 1; (4) B̃ (i) i,n(0) = n! (n− i)! ( 1 + n− 2i+ 1 (n− i+ 1)(n− 1)λ ) (5) By Definition 1, (3) is obvious. By (2) and the properties of Bernstein basis at the endpoints, it’s easy to prove (4) and (5). • Linear independence n∑ i=0 ciB̃i,n(t) = 0 ⇔ ci = 0 for all i By taking t = 0 and t = 1, we get from (3) that c0 = 0 and cn = 0. Differentiating the linear combination i times we deduce from (4) that ciB̃ (i) i,n(0) = 0 for i = 1, . . . , n − 1. Then by (5), B̃(i)i,n(0) > 0, we have ci = 0, i = 1, . . . , n − 1. Therefore, ci = 0 for all i. That is, B̃i,n(t)(i = 0, 1, . . . , n) are linearly independent. • Symmetry B̃i,n(t) = B̃i,n−i(1− t) t ∈ [0, 1] • Integrals∫ 1 0 B̃0,n(t)dt = ∫ 1 0 B̃n,n(t)dt = n+ 2− λ (n+ 1)(n+ 2)∫ 1 0 B̃i,n(t)dt = 1 n+ 1 + 2λ (n2 − 1)(n+ 2) where i = 1 . . . n− 1. • Positivity B̃i,n(t) ≥ 0 t ∈ [0, 1], λ ∈ [−1, 1] (6) • Unimodality A function is said to be unimodal if it has only one local maximum. B̃i,n(t) are unimodal in t. Proof: The unimodal is obvious for B̃0,n(t) and B̃n,n(t). For i = 1 . . . n − 1, consider the graph of the function B̃i,n(t), that is, the curve S(t) = (t, B̃i,n(t)). We can rewrite (2) as B̃i,n(t) = n+1∑ k=0 PkBk,n+1 where Pi = n+ 1− i n+ 1 + n− 2i+ 1 n2 − 1 λ (7) Pi+1 = i+ 1 n+ 1 − n− 2i− 1 n2 − 1 λ (8) Pk = 0 , k �= i, i+ 1 0 0.2 0.4 0.6 0.8 1 Fig. 2. Graph of B̃2,5(t) with λ = 1(light) together with its control polygon (dark). and we also have t = ∑n+1 k=0 k n+1Bk,n+1(t). Therefore, S(t) = ∑n+1 k=0( k n+1 , Pk)Bk,n+1(t). Thus S(t) is a Bézier curve of degree n+1, and the control points for the graph of B̃i,n(t) all lie along the t-axis except for the points at( i n+1 , Pi ) and ( i+1 n+1 , Pi+1 ) . From (7), (8) Pi > 0 and Pi+1 > 0. Therefore, the control polygon for the graph of B̃i,n(t) has only one local maximum (see Fig. 2 ). But the graph of B̃i,n(t) is a Bézier curve, and Bézier curves are variation diminishing. Therefore, the graph of B̃i,n(t) can oscillate no more than its control polygon. Hence B̃i,n(t) has only one local maximum. • Partition of unity n∑ i=0 B̃i,n(t) = 1 (9) Substitutes (2) in the (9), it is easy to get this property. IV. PROPERTIES OF THE BÉZIER CURVE WITH SHAPE PARAMETER A Bézier curve with shape parameter P (t) with control points Pi is defined by P̃ (t) = n∑ i=0 PiB̃i,n(t) t ∈ [0, 1] (10) where B̃i,n(t) is Bézier basis with shape parameter • Geometric properties at the endpoints The geometric properties at the endpoints of the Bézier curves with shape parameter can be easily deduced from those of the Bézier basis with shape parameter. P̃ (0) = P0 P̃ (1) = Pn, (11) P̃ (j)(0) = j∑ i=0 PiB̃ (j) n,n(0), P̃ ′(0) =(n+ λ)(P1 − P0) P̃ ′(1) =(n+ λ)(Pn − Pn−1) (12) 1713 ThP13.3 0 2 4 6 8 10 12 14 −1 0 1 2 3 4 5 6 7 8 9 λ = 1 λ = −1 λ = 0 Fig. 3. The cubic Bézier curve of with shape parameter λ = −1, 0, 1 It means the curve interpolate at the endpoints and tangent at the end edge. Suppose then that we are given a Bézier curve with shape parameter B̃(t) = ∑ i B̃i,n(t)Pi and we want to construct another Bézier curve with shape parameter C̃(t) = ∑ i B̃(t)Qi that meets B̃(t) and hold G1 continue at its end point. Then from Equations (11) and (12) we get Q0 = Pn Q1 −Q0 = c(Pn − Pn−1) and change the λ don’t effect the G1 continue of the curves. Fig. 3 shows this property. • Affine invariance By (6) and (9), affine invariance is obviously. It asserts that the curve is independent of the choice of the coordi- nate system. • Convex hull property n∑ i=0 PiB̃i,n(t) ⊆ ConvexHull{P0, . . . , Pn}. This property is a consequence of (6) and (9). Fig. 3 shows convex hull property. • Symmetry P̂ (1− t) = n∑ i=0 B̃i,n(1− t)Pn−i = n∑ i=0 B̃i,n(t)Pi = P̃ (t) • Degenerate P̃ (t) = P (t) when λ = 0. • Variation Diminishing Bézier curves with shape parameter are variation dimin- ishing. Proof: By (2) we have n∑ i=0 PiB̃i,n+1(t) = n+1∑ i=0 QiBi,n+1(t) where Q0 = P0 Qi = i− n−2i+1n−1 λ n+ 1 Pi−1 + n+ 1− i+ n−2i+1n−1 λ n+ 1 Pi Qn+1 = Pn Thus Qi(i = 1, . . . , n) is a convex combination of Pi−1 and Pi. Hence point Qi lies on the line joining Pi−1 and Pi. We illustrate this algorithm for cubic curves in Figure 4. Q0=P0 Q3 Q4=P3 Q2P1 Q1 P2 Fig. 4. A cubic Bézier curve with shape parameterλ = −0.8. The points {P0, P1, P2, P3} are the control points for the cubic Bézier curve B(t) with shape parameter, and the points {Q0, Q1, Q2, Q3, Q4} represent the same curve B(t) as a quartic Bézier curve. Notice in Fig. 4 that the control polygon Q = (Q0, Q1, Q2, Q3, Q4) is obtained from the original con- trol polygon P = (P0, P1, P2, P3) by cutting off the corners at P1 and P2. Corner cutting reduces the oscillation of a polygon [4]. If Q(t) is the piecewise linear curve obtained by cutting corners off of another piecewise linear curve P (t), then any line L intersects P (t) at least as often as it intersects Q(t) because if a line intersects one side of a triangle, then it must intersect one of the other two sides. Thus corner cutting is a variation diminishing process.That is number of intersections of Q(t) and L ≤ number of intersections of P (t) and L. On the other hand, Bézier curves are variation diminishing [4]. number of intersections of B̃(t) and L ≤ number of intersections of Q(t) and L ≤ number of intersections of P (t) and L. • Some examples Fig. 5 a and b respectively show the hexagon consisting of six symmetric control polygons and the flowers consisting of six symmetric quartic and cubic Bézier curves with 1714 ThP13.3 shape parameter for λ = 1, 0,−1 (dashed, solid and dashed-dot lines). Fig. 5 c and d respectively show the square consisting of four symmetric control polygons and the flowers consisting of four symmetric quartic and cubic Bézier curves with shape parameter for λ = 1, 0,−1 (dashed, solid and dashed-dot lines). The symbol � is the control point in all figures. Fig. 3 shows degree-3 Bézier curves with shape parameter for λ = 1, 0,−1 (dashed, solid and dashed-dot lines). The figures show that the Bézier curves with shape parameter approximate to the control polygon as the increase of the shape parameter. a b c d Fig. 5. The flowers consisting of symmetric Bézier curves with shape parameter V. BÉZIER SURFACE WITH SHAPE PARAMETER The rectangular surfaces of tensor product with control points Pi,j are defined by S̃(s, t) = m∑ i=0 n∑ j=0 B̃i,m(s)B̃j,n(t)Pi,j where B̃i,m(s) and B̃j,n(t) are the Bézier basis functions with shape parameter, and Pi,j is the control point. The tensor product of Bézier surface with shape parameter has properties similar to those of the tensor product of Bézier surface. Let λs, λt denote the shape parameter on s, t, we have following properties λs=1,λt=1 λs=−1,λt=1 λs=−1,λt=−1 λs=0,λt=0 Fig. 6. Bézier curves with shape parameters • Corner values B̃i,m(0)B̃j,n(0) = 1 i = 0, j = 0 = 0 others B̃i,m(0)B̃j,n(1) = 1 i = 0, j = n = 0 others B̃i,m(1)B̃j,n(0) = 1 i = m, j = 0 = 0 others B̃i,m(1)B̃j,n(1) = 1 i = m, j = n = 0 others • Boundary values B̃i,m(s)B̃j,n(0) = 0 j �= 0 = B̃i,m(s) j = 0 B̃i,m(s)B̃j,n(1) = 0 j �= n = B̃i,m(s) j = n B̃i,m(0)B̃j,n(t) = 0 i �= 0 = B̃j,n(t) i = 0 B̃i,m(1)B̃j,n(t) = 0 i �= m = B̃j,n(t) i = m • Linear independence m∑ i=0 n∑ j=0 cijB̃i,m(s)B̃j,n(t) = 0 ⇔ cij = 0 for all ij Proof: If we fix s, by the linear independence of B̃j,n(t), we get ∑m i=0 cijB̃i,m(s) = 0. Since s is arbi- trarily and we also have B̃i,m(s) is linear independence, we obtain cij = 0. • Positivity B̃i,m(s)B̃j,n(t) ≥ 0 1 ≥ s, t ≥ 0, λs, λt ∈ [−1, 1] • Partition of unity m∑ i=0 n∑ j=0 B̃i,m(s)B̃j,n(t) = 1 1715 ThP13.3 • Symmetries B̃i,m(s)B̃j,n(t) = B̃i,m−i(1− s)B̃j,n−j(1− t) from the properties of the basis functions, it’s easy to obtained the following properties • Interpolate at the corner-point and is tangent at the corner- plane S̃(0, 0) = P0,0 S̃(0, 1) = P0,n S̃(1, 0) = Pm,0 S̃(1, 1) = Pm,n in fact, the edges of the surface are the kind of curves defined by difinition 1; S̃(s, 0) = ∑m i=0 Pi,0B̃i,m(s) S̃(s, 1) = ∑m i=0 Pi,nB̃i,m(s) S̃(0, t) = ∑n j=0 P0,jB̃j,n(t) S̃(1, t) = ∑n j=0 Pm,jB̃j,n(t) • Convex hull property; • Geometric invariability and affine invariability; • S̃(s, t) degenerate to Bézier Surfaces when λs = λt = 0. With different shape parameters, the shape of surface can be modified variously (Fig. 6). Specially, when λs = λt = 0, the surface is just the original Bzier surface (the last surface in Fig. 6). Acknowledgment The work was supported by the Natural Science Foundation of Fujian Province of China (No. 2010J01012). REFERENCES [1] Carnicer J.M. and Pena, J.M., Shape preserving representations and optimality of the Bernstein basis, Adv. Computer Math., (1993), 1: 173- 196. [2] Cheng H.H., Zeng X.M., Bézier curves with shape parameter, Journal of Xiamen Univ. (Natural Science, in Chinese), (2006), 45: 320-322. [3] Farin G. Curves and Surfaces for Computer Aided Geometric Design, 5th ed, Elsiver Inc. 2002. [4] Goldman R.N., Pyramid Algorithms: A dynamic Programming Approach to Curves and Surfaces for Geometric Modeling, Elsiver Inc. 2003. [5] Han X.L., Quadratic trigonometric polynomial curves with a shape parameter, Computer Aided Geometric Design, (2002), 19: 503-512. [6] Han X.L., Cubic trigonometric polynomial curves with a shape param- eter, Computer Aided Geometric Design, 21: 535-548. [7] Wang W.T. and Wang G.Z., Bézier curve with shape parameter, Journal of Zhejiang Univ. Sci., (2005), 6A(6): 497-501 [8] Yang L.Q. and Zeng X.M., Bézier curves and surfaces with shape parameters, International Journal of Computer Mathematics, (2009), 86: 1253-1263. 1716 ThP13.3 /ColorImageDict > /JPEG2000ColorACSImageDict > /JPEG2000ColorImageDict > /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 200 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages false /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict > /GrayImageDict > /JPEG2000GrayACSImageDict > /JPEG2000GrayImageDict > /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 400 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 600 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict > /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description > >> setdistillerparams > setpagedevice