Normal approximations of regular curves and surfaces

Filomat 29:3 (2015), 457–464 DOI 10.2298/FIL1503457C Published by Faculty of Sciences and Mathematics, University of Niˇ s, Serbia Available at: http://www.pmf.ni.ac.rs/filomat Normal Approximations of Regular Curves and Surfaces Alfonso Carriazoa, M. Carmen M´arqueza, Hassan Ugailb aDepartment of Geometry and Topology, Faculty of Mathematics, University of Seville, c/Tarfia s/n, 41012-Seville, SPAIN bCentre for Visual Computing, University of Bradford, Bradford BD7 1DP, UNITED KINGDOM Abstract. B´ ezier curves and surfaces are two very useful tools in Geometric Modeling, with many applications. In this paper, we will offer a new method to provide approximations of regular curves and surfaces by B´ ezier ones, with the corresponding examples. 1. Introduction The classic theory of curves and surfaces is one of the most famous areas in Differential Geometry. It combines very visual and intuitive elements with really deep results and techniques. This theory was mainly developed in the 18th and 19th centuries, by mathematicians like Gaspard Monge (1746-1818), who is considered the father of Differential Geometry because of his work Application de l’Analyse `a la G´eom´etrie, or Carl Friedrich Gauss (1777-1855), among many others. But the direct use of regular curves and surfaces in applied areas such as engineering or architecture is not easy in general. There, some other types of geometrical tools have been developed. For example, B´ ezier curves and surfaces, named after the French Engineer and Mathematician Pierre B´ ezier (1910-1999). They have proved to be two very useful tools in Geometric Modeling, with many applications. In this paper, we want to strengthen the link between these two geometrical theories, offering an answer to this main question: given a regular curve or surface, is it possible to approximate it by a B´ ezier one? Of course, this question is not new, and have been deeply studied in some particular cases (see, for instance, [1] and [2]). But we offer a different approach, with a method which can be used for any kind of regular curve or surface. In fact, our method is somehow inspired by a classical construction in Differential Geometry: the orthogonal variations. Roughly speaking, an orthogonal variation of a curve is produced when the curve is considered as a cord, vibrating in a direction which is orthogonal to its tangent vector at any point. Variations of curves are used, for example, to characterize geodesics as the solutions of a variational problem. For more details and the exact definitions about this procedure, we recommend [3]. Our method can be seen as a kind of discretization of that construction. 2010 Mathematics Subject Classification. Primary 65D17; Secondary 53A04, 53A05 Keywords. Regular curve, regular surface, B´ ezier curve, B´ ezier surface, normal approximation. Received: 21 August 2014; Accepted: 26 January 2015 Communicated by Mica Stankovic, Ljubica Velimirovic The first two authors are partially supported by the MINECO-FEDER grant MTM2011-22621. The first author is also partially supported by the PAIDI group FQM-327 (Junta de Andaluc´ ıa, Spain). The first two authors want to express their gratitude to their colleague Prof. M. A. Jap´ on, for her very useful advices. Email addresses: [email protected] (Alfonso Carriazo), [email protected] (M. Carmen M´ arquez), [email protected] (Hassan Ugail) Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 458 2. Preliminaries In this section, we recall some definitions and basic formulas which we will use later. Aregular parametrized plane (resp. spatial)curve is a differentiable map α:I→R2(resp. R3) of an open interval I=(a,b) of the real line Rinto R2(resp. R3), such that α′(t),0 for any t∈I. We can consider also a curve αdefined on a closed interval [c,d] if there exist an open interval (a,b) and a curve ¯ αdefined on (a,b) such that [c,d]⊂(a,b) and α(t)=¯ α(t), for any t∈[c,d] (i.e., αis the restriction of ¯ α). Given a regular parametrized plane curve α:I→R2:t7→ α(t)=(x(t),y(t)), we can consider a moving orthonormal dihedron {t,n}along α, called the Frenet dihedron, defined by: t(t)=α′(t) |α′(t)|=1 |α′(t)|(x′(t),y′(t)),n(t)=1 |α′(t)|(−y′(t),x′(t)). The vector tis called the unit tangent vector and nis known as the normal vector. For a spatial curve α, we first recall that its curvature is given by k=|α′×α′′| |α′|3. Therefore, at every point α(t) such that k(t),0, we can consider an orthonormal trihedron {t(t),n(t),b(t)}, called the Frenet trihedron, defined by: t(t)=α′(t) |α′(t)|,b(t)=α′(t)×α′′(t) |α′(t)×α′′(t)|,n(t)=b(t)×n(t). The vector tis called the unit tangent vector,nis the principal normal vector and bis known as the binormal vector. Aregular parametrized surface is a differentiable map x:U→R3: (u,v)7→ x(u,v) of an open set Uof the real plane R2into R3, such that ∂x/∂u×∂x/∂v,0 at any point (some authors also ask such a surface to be injective). This regularity condition allows us to define the normal vector at any point of the surface, given by: N=∂x/∂u×∂x/∂v |∂x/∂u×∂x/∂v|. For more details about regular curves and surfaces, we recommend the classical reference [3]. Let us recall now the definitions of B´ ezier curves and surfaces. Given n+1 points P0, . . . , Pn, they determine the B´ezier curve B : [0,1] →R2(or R3) given by B(t)= n ∑ i=0 Bn i(t)Pi, where Bn i(t)=(n i)ti(1 −t)n−i,0≤i≤n is the Bernstein polynomial of degree n. Given a grid of m·npoints Pij, 0 ≤i≤m,0≤j≤n, it determines the B´ezier surface B : [0,1] ×[0,1] →R3given by B(u,v)= m ∑ i=0 n ∑ j=0 Bm i(u)Bn j(v)Pij, where Bm iand Bn jare Bernstein polynomials of degree mand n, respectively. For more details about B´ ezier curves and surfaces, we recommend the reference [4]. Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 459 3. Normal approximation of regular curves Let α: [0,1] −→ R2be a regular parametrized plane curve. We want to approximate it by a B´ ezier curve, which will be determined by n+1 control points P0,P1,...,Pnin R2. We now describe our method to choose these points: •Step 1: We choose n+1 values t0, . . . , tnin [0,1] such that t0=0<t1<··· <tn−1<tn=1. We directly put P0=α(0), Pn=α(1). For every i=1, . . . , n−1, we consider the point Pi(λi)=α(ti)+λin(ti),(1) where λiis a real parameter and n(ti) is the normal vector to αat α(ti). This means that the point Pi(λi) lies on the normal line to αat α(ti) (see Figure 1) α(ti) α(0) α(1) Pi(λi) n(ti) t(ti) Figure 1: Point Pi(λi) on the normal line to αat α(ti). •Step 2: We construct the B´ ezier curve B(λ1, . . . , λn−1,t)=Bn 0(t)P0+ n−1 ∑ i=1 Bn i(t)Pi(λi)+Bn n(t)Pn,(2) depending on the parameters λ1, . . . , λn−1, where Bn i(t) are the usual Bernstein polynomials. •Step 3: We define the function: F(λ1, . . . , λn−1)=∫1 0|α(t)−B(λ1, . . . , λn−1,t)|2dt.(3) This function is, in fact, the squared semimetric in L2([0,1]). It represents the error between α(t) and B(λ1, . . . , λn−1,t). •Step 4: In order to obtain the best possible approximation with this method, we minimize the above function, finding values λ0 1, . . . , λ0 n−1. Then, the B´ ezier curve we are looking for is B(λ0 1, . . . , λ0 n−1,t), which is determined by the control points P0,P1(λ0 1), . . . , Pn−1(λ0 n−1),Pn. Let us notice how this can be done just by solving a linear equations system given by ∂F/∂λj=0, for any j=1, . . . , n−1. In fact, by applying the usual “differentiation under the integral sign” criterion, it follows from (3) that ∂F ∂λj =∫1 0 ∂G ∂λj dt, Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 460 where G(λ1, . . . , λn−1,t)=|α(t)−B(λ1, . . . , λn−1,t)|2 = 2 ∑ k=1 (αk(t)−Bk(λ1, . . . , λn−1,t))2, αk(t) (resp. Bk(λ1, . . . , λn−1,t)) being the k-th component of α(t) (resp. B(λ1, . . . , λn−1,t)). Therefore: ∂G ∂λj =2 2 ∑ k=1 (αk(t)−Bk(λ1, . . . , λn−1,t))∂(αk(t)−Bk(λ1, . . . , λn−1,t)) ∂λj . But it easily follows from (1) and (2) that ∂(αk(t)−Bk(λ1, . . . , λn−1,t)) ∂λj =−Bn j(t)nk(tj), where nk(tj) denotes the k-th component of n(tj). Thus, ∂F ∂λj =−2 2 ∑ k=1 nk(tj)∫1 0 (αk(t)−Bk(λ1, . . . , λn−1,t))Bn j(t)dt =−2 2 ∑ k=1 nk(tj)(∫1 0 αk(t)Bn j(t)dt −Pk 0∫1 0 Bn 0(t)Bn j(t)dt − n−1 ∑ i=1 αk(ti)∫1 0 Bn i(t)Bn j(t)dt −Pk n∫1 0 Bn n(t)Bn j(t)dt       +2 n−1 ∑ i=1       2 ∑ k=1 nk(ti)nk(tj)∫1 0 Bn i(t)Bn j(t)dt       λi, where we have used (1) and (2) again. This expression is clearly linear in λ1, . . . , λn−1. Example 3.1. Let α: [0,1] −→ R2be the parabola given by α(t)=(t,t2). If we want to approximate αwith just an intermediate point, we put n =2and we directly have P0=α(0) =(0,0) and P2=α(1) =(1,1). We choose t1=1/2and construct P1(λ1)=α(1/2) +λ1n(1/2) =(1 2−√2 2λ1,1 4+√2 2λ1). Therefore, the B´ezier curve depending on parameter λ1is given by: B(λ1,t)=B2 0(t)P0+B2 1(t)P1(λ1)+B2 2(t)P2 =(2(1 −t)t(1 2−√2 2λ1)+t2,2(1 −t)t(1 4+√2 2λ1)+t2). Now, we calculate the function appearing in Step 3, resulting: F(λ1)=∫1 0|α(t)−B(λ1,t)|2dt =2 15λ2 1+√2 30 λ1+1 120. Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 461 To minimize this function, we impose ∂F/∂λ1=0, and we obtain the linear equation 4 15λ1+√2 30 =0, whose solution is λ0 1=−√2/8. Therefore, our control point is P1(λ0 1)=(5/8,1/8) and the corresponding B´ezier curve is: B(λ0 1,t)=(5 4(1 −t)t+t2,1 4(1 −t)t+t2). The error is given by F(λ0 1)=0.004166666667. In Figure 2 we can see both the real curve α(t)(in blue) and its approximation B(λ0 1,t)(in red). We represent in green the control points P0,P1(λ0 1),P2. Figure 2: Approximation of a parabola. If we choose more intermediate control points, we obtain better approximations. The error estimates can be seen in the following table. In all cases, we have chosen the values tiuniformly distributed. n error estimate 2 0.004166666667 3 0.001459250709 4 0.0008372327736 We can improve our method if we take into account a well-known fact for B´ ezier curves: the derivatives at the endpoints are completely determined. In fact, if B(t) is a B´ ezier curve given by control points P0,P1, . . . , Pn, then B′(0) =n(P1−P0),B′(1) =n(Pn−Pn−1). In our case: B′(λ1, . . . , λn−1,0) =n(α(t1)+λ1n(t1)−α(0)), B′(λ1, . . . , λn−1,1) =n(α(1) −α(tn−1)−λn−1n(tn−1)). If we impose for the B´ ezier curve B(λ1, . . . , λn−1,t) of Step 2 that its tangent directions at the endpoints P0and Pnare the same as those of the curve α(t), i.e., B′(λ1, . . . , λn−1,0) ·n(0) =0,B′(λ1, . . . , λn−1,1) ·n(1) =0,(4) then we obtain two linear equations easily determining λ0 1, λ0 n−1. We follow our method to obtain the other parameters λ0 2, . . . , λ0 n−2and we say that the B´ ezier curve B(λ0 1, . . . , λ0 n−1,t) is “clamped” at the endpoints P0,Pn. Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 462 Example 3.2. We apply the above improvement to the parabola of Example 3.1. As we will easily determine control points P1(λ1)and Pn−1(λn−1), we put n =4and we directly have P0=(0,0) and P4=(1,1). We choose t1=1/4,t2=1/2,t3=3/4and we construct P1(λ1),P2(λ2),P3(λ3)in our usual way. Now, we write equations from (4): 1 4+4√20 5λ1=0,−√5 20 −32 √65 65 λ3=0. The solutions are λ0 1=−√5/32 and λ0 3=−√13/128. They completely determine P1(λ0 1)and P3(λ0 3). Therefore, we only have to obtain the value for the parameter λ2of the B´ezier curve B(λ0 1, λ2, λ0 3,t)by minimizing the function F(λ0 1, λ2, λ0 3). The result is λ0 2=−59 √2/1536 and the error is now F(λ0 1, λ0 2, λ0 3)=0.000873819987, which is smaller than F(λ0 1)from Example 3.1. This method to approximate plane curves can also be adapted for spacial curves, i.e., curves in R3. In such a case, n(ti) would be the principal normal vector to αat α(ti) (see Figure 3). To do so, we need κ(ti),0, where κ(t) denotes the curvature of α(t) (if not, n(ti) is not defined). Therefore, we should be more careful with the choosing of the values of t1, . . . , tn−1. α(ti) α(0) α(1) Pi(λi) n(ti) t(ti) b(ti) Figure 3: Point Pi(λi) on the principal normal line to αat α(ti). Example 3.3. Let α: [0,1] −→ R3be the circular helix given by α(t)=(cos(2πt),sin(2πt),t). In Figure 4 we show the approximations (in red) of α(in blue) for n =2,3,4,5, i.e., with 3,4,5,6control points (in green), respectively. The error estimates can be seen in the following table: n error estimate 2 0.5830658815 3 0.1466088404 4 0.04716853518 5 0.02161578330 Let us notice how the approximation for n =2is very bad, because a B´ezier curve determined by 3control points is always a plane curve. Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 463 Figure 4: Approximations of a circular helix. 4. Normal approximation of regular surfaces Let x: [0,1] ×[0,1] −→ R3be a regular parametrized surface. We want to approximate it by a B´ ezier surface, which will be determined by a grid of m·ncontrol points Pij in R3. We follow these steps to choose the points: •Step 1: We approximate the border curves α1(t)=x(t,0), α2(t)=x(0,t), α3(t)=x(t,1), α4(t)=x(1,t), by B´ ezier curves B1(t), . . . , B4(t), by following the method described in Section 3. Therefore, we determine the exterior points of the control grid. For the interior points of the control grid, we write Pij(λij)=x(ui,vj)+λijN(ui,vj), where λij is a real parameter and N(ui,vj) is the normal vector to xat x(ui,vj). This means that the point Pij(λij) lies on the normal line to xat x(ui,vj). •Step 2: We construct the B´ ezier surface B(λij,u,v), depending on the parameters λij. •Step 3: We define the function: F(λij)=∫1 0∫1 0|x(u,v)−B(λij,u,v)|2dudv. Alfonso Carriazo et al. /Filomat 29:3 (2015), 457–464 464 •Step 4: We minimize the above function, finding values λ0 ij. Then, the B´ ezier surface we are looking for is B(λ0 ij,u,v), and the interior points of the control grid are Pij(λ0 ij). Example 4.1. Let x: [0,1] ×[0,1] −→ R3be the piece of a circular cylinder given by x(u,v)=(u,cos(πv),sin(πv)) and shown in the first frame of Figure 5. The border curves are painted in blue. To follow the above described method, we begin by approximating the border curves by B´ezier curves with n =3. This will produce a grid of 16 control points (with 4interior points). The obtained B´ezier curves are shown in the second frame of Figure 5. Let us notice how, given that α1and α3are just line segments, B1(t)=α1(t)and B3(t)=α3(t), and the corresponding control points lie on these line segments. We then follow our method to determine the interior control points. The resulting B´ezier surface is shown in the third frame of Figure 5. Its border is given by B´ezier curves B1(t), . . . , B4(t). Figure 5: Approximation of a piece of circular cylinder. With this method we can approximate any regular parametrized surface. For example, approximations of a piece of a helicoid, a catenoid and a torus are shown in Figure 6. Figure 6: Approximations of helicoid, catenoid and torus. References [1] Y. J. Ahn, Helix approximations with conic and quadratic B´ ezier curves, Computer Aided Geometric Design 22 (2005) 551–565. [2] Y. J. Ahn, Y. S. Kim, Y. Shin, Approximation of circular arcs and offset curves by B´ ezier curves of high degree, Journal of Computational and Applied Mathematics 167 (2004) 405–416. [3] M. P. do Carmo, Differential Geometry of Curves and Surfaces, Prentice-Hall, Englewood Cliffs, New Jersey, 1976. [4] G. Farin, Curves and Surfaces for CAGD, Morgan Kaufman, San Francisco, 2001.