英文翻译.pdf

A constrained guided G1continuous spline curve D.S. Meek*, B.H. Ong1, D.J. Walton Department of Computer Science, University of Manitoba, Winnipeg, Canada R3T 2N2 Received 23 December 2001; revised 1 March 2002; accepted 5 March 2002 Abstract A method for drawing a guided G1continuous planar spline curve that falls within a closed boundary is presented. The curve is composed of segments of quadratic polynomials (parabolas) and rational quadratics (conics) that join with continuous unit tangent vectors. The boundary is composed of straight line segments and circular arcs. q 2002 Published by Elsevier Science Ltd. Keywords: Guided G1spline curve; Constrained curve 1. Introduction A method for drawing a guided G1continuous planar spline curve that falls within a closed boundary is presented. The curve is composed of segments of quadratic poly- nomials (parabolas) and rational quadratics (conics) that join with continuous unit tangent vectors. The boundary is composed of straight-line segments and circular arcs. There are several problems whose solution requires this type of method. A user may wish to design a curve that fi ts inside a given region as, for example, when one is designing a shape to be cut from a fl at sheet of material. A user may wish to design a smooth path that avoids obstacles as, for example, when one is designing a robot path. The problem of drawing constrained curves has been discussed previously. In Ref. 2, a G2continuous, shape- preserving curve made of rational cubics that interpolates to given points and that lies on one side of a line, or several lines, is described. In Ref. 4, fair Be zier curves with fi xed cross-sectional area are produced. In Ref. 5, a G2 continuous curve made of rational cubics that interpolates to given points inside an arbitrary polygon is presented. In Ref. 1, a C1continuous non-parametric interpolating rational (cubic numerator and linear denominator) that lies above, below, or between polylines is discussed. In Ref. 6, a G2continuous curve made of non-parametric rational cubics that lies on one side of a line, or one side of a quadratic curve is found. In Ref. 7, a C1continuous shape- preserving interpolating cubic spline with minimum curva- ture is produced. The curve is constrained to lie inside an arbitrary polygon. In this paper, the boundary consists of straight line segments and circular arcs, which is different than boundaries considered by other papers. The curve here is quadratic, most other results use cubics, and the quadratic generally results in simpler theory and simpler algorithms. Finally, the curve here is guided by control points rather than by the more commonly used interpolation points. Theuserguidesthecurvewithcontrolpointsofaquadratic B-spline with uniform knots. In the simplest case, Section 3, the B-spline control polyline does not intersect the boundary. A B-spline can be expressed as a set of Be zier curves. If a particularquadraticBe ziercurvedoesnotintersectanypartof the boundary, it is accepted. If it does intersect any part of the boundary, then it is replaced by a rational quadratic Be zier curve that has the same Be zier control points, but which does notintersecttheboundary.TheuseofthesameBe ziercontrol points ensures that the collection of Be zier curves forms a G1 continuous curve. The method described in Section 3 can always determine a rational quadratic curve that does not intersect the boundary (see Theorem 1). In Section 4, the B- spline control polyline is allowed to intersect the boundary at some points, and a curve that does not cross the boundary can often be produced. A user could manipulate the B-spline control points interactively to cause the curve to fall within the boundary rather than use the method presented in this paper. However, the method here attempts to aid the user by partly automating the process. The method here can also give a 0010-4485/03/$ - see front matter q 2002 Published by Elsevier Science Ltd. PII: S0010-4485(02)00086-6 Computer-Aided Design 35 (2003) 591599 1 Visiting from Universiti Sains Malaysia, 11800 Penang, Malaysia. *Corresponding author. Tel.: 1-204-474-8681; fax: 1-204-474-7609. E-mail address: dereck_meekumanitoba.ca (D.S. Meek). curve that passes exactly (within computational accuracy) through a corner of the boundary, or that is exactly tangent to the boundary. Those results could be diffi cult to achieve interactively. The method used here also gives more localized control as only one Be zier segment may be changed to avoid crossing the boundary, while adjusting a B-spline control point will cause three Be zier segments to change. Special requirements such as having the curve tangent to a line segment of the boundary, having the curve run along a line segment of the boundary, and having a cusp on the boundary are discussed at the end of Section 3. 2. Some results on rational quadratic Be zier curves Consider the family (parameter w) of rational quadratic Be zier curves B(t,w) with non-zero area Be zier control triangle B0B1B2, Bt;w Qt;w qt;w 1 2 t2B0 2w1 2 ttB1 t2B2 1 2 t2 2w1 2 tt t2 ; 0 , t , 1; 0 , w , 1;1 The members of this family of curves are segments of conics: w , 1 gives a segment of an ellipse, w 1 gives a segment of a parabola, and w . 1 gives a segment of a hyperbola 3. Although the curves as defi ned in Eq. (1) do not allow w 0 or w tending to infi nity, these two extreme w-values are of interest. If these values were allowed, B(t,0) would be the line segment B0B2, while B(t,1) would be the point B1(see Fig. 1). Result 1: Location of curves (1). The points on a curve (1) are a weighted average of the control points B0, B1, and B2. With the restrictions on t and w in Eq. (1), all of the weights are positive, so all points B(t, w) are strictly inside the control triangle B0B1B23 (see Fig. 2).A Result 2: The curve (1) that passes through a given point. The w-value of the curve (1) that passes through a given point P can be found as described later. Since all points on the curves (1) are strictly inside the control triangle B0B1B2 (Result 1), P must be strictly inside as well. The development below fi nds the t in (0,1) and w in (0,1) such that Bt;w P: Since P B1, consider the intersection of the line through B0and B2, 1 2 rB0 rB2; with the line through B1and P, 1 2 sB1 sP (see Fig. 1). The r and s values at the intersection point are r B12 P B12 B0 B12 P B22 B0 s B12 B0 B22 B0 B12 P B22 B0 ; 2 wherestands for the scalar cross product of two- dimensional vectors. Since P is inside control triangle B0B1B2, 0 , r , 1 and 1 , s. The point of intersection for a given t is also B(t,0), and this allows the solution of t independently of w 3. The line B0B2is from Eq. (1) Bt;0 1 2 t2B0 t2B2 1 2 t2 t2 :3 so a quadratic equation for t is t2 1 2 t2 t2 r:4 Since 0 , r , 1, there is exactly one root t in (0,1). This root can be found by writing Eq. (4) as 1 2 t t ?2 1 2 r r ; solving for 1 2 t=t; which must be positive, and fi nally solving for t to give t ffiffi r p ffiffi r p ffi ffi ffi ffi ffi ffi ffi 1 2 r p;5 which is in (0,1) for 0 , r , 1. The vectors B(t,0) 2 P and P 2 B1are parallel and, since 1 , s, are pointing in the Fig. 1. Curve (1) passing through a given point P. Fig. 2. Curves (1) fi lling the control triangle and nested. D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599592 same direction, or Bt;0 2 PP 2 B1 . 0:6 Substitution of formula (3) in Eq. (6) shows that 1 2 t2B02 PP 2 B1 t2B22 PP 2 B1 . 0: 7 Once the t value in Eq. (5) is found, the unique corresponding positive (see Eq. (7) value for w is, from Eq. (1), w 1 2 t2B02 PP 2 B1 t2B22 PP 2 B1 21 2 ttP 2 B1P 2 B1 : 8 A The earlier two results are summarized in lemma 1. Lemma 1. If P is strictly inside the Be zier control triangle B0B1B2, then there is a unique curve (1) that passes through P. If P is not inside the control triangle, then there is no curve (1) that passes through P. The t- and w-values such that Bt;w P are given by Eqs. (5), (2) and (8). Result 3: Control triangle fi lling and nesting property. Result 2 shows that there is a unique curve (1) through any point P strictly inside the control triangle B0B1B2. This fact means the curves (1) completely fi ll the interior of the triangle B0B1B2. The fact that the curve (1) through any point P is unique means two curves (1) with different w- values cannot intersect inside the control triangle as an intersection point would be a point through which more than one curve passes (see Fig. 2). The partial derivative of Eq. (1) with respect to w is the vector Bwt;w 21 2 tt1 2 t2 t2? 1 2 t2 2w1 2 tt t2?2 B12 Bt;0: The direction of this vector is constant with respect to w, so the locus of points B(t,w) with fi xed t and increasing w is a straight line from B(t,0) to B1. Thus, the family of curves (1) forms a nested set of curves as w moves from 0 to 1; the curve (1) as w tends to 0 is the line segment B0B2, while the curve (1) as w tends to 1 is the polyline with segments B0B1 and B1B2. If a curve (1) with a certain w is drawn, then all curves (1) with higher w-values are between that curve and the polyline B0B1B2.A Result 4: The curve (1) that is tangent to a given line segment. The w-value of the curve (1) that is tangent to a given line segment S0S1(S0and S1are distinct) can be found as described later in this Result. This result is used in the method described in Section 4. The procedure is fi rst to fi nd a curve (1) that is tangent to the infi nite line L through the points S0and S1, and then to determine if the point of tangency is in the segment S0S1. The line L must pass through the control triangle for a tangent to be possible (see Fig. 3). It will now be argued that a tangent line L cannot cut B0B2and cannot pass through B1. Curve (1) is a segment of a conic and conics have the property that they do not cross any of their tangent lines. The curve (1) joins B0to B2, so it would cross any line that cuts B0B2; thus, a tangent line L cannot cut B0B2. In particular, L cannot pass through B1and cross B0B2. If L passes through B1and does not cross B0B2, then curves (1) cannot be tangent to L because L does not enter the control triangle B0B1B2. Thus, a tangent line L cannot pass through B1. In the calculations that follow, fi rst check that L is a tangent to the curve B(t,w) and then check that the point of tangency is in the segment S0S1. If a curve (1) is tangent to line L, then the point of tangency B(t,w) must be on L, or Bt;w 2 S0 S12 S0 0;9 and the partial derivative of B(t,w) with respect to t must be parallel to L, or Btt;w S12 S0 0:10 Using Eq. (1), Eq. (9) can be rewritten, Qt;w 2 qt;wS0 S12 S0 0:11 Differentiation of the relation qt;wBt;w Qt;w from Eq. (1) with respect to t gives qtt;wBt;w qt;wBtt;w Qtt;w:12 Taking the cross product of both sides of Eq. (12) on the right by S12 S0and using Eqs. (9) and (10) gives Qtt;w 2 qtt;wS0 S12 S0 0:13 The left side of Eq. (11) is the quadratic in t 1 2 t2B02 S0 S12 S0 2w1 2 ttB12 S0 S12 S0 t2B22 S0 S12 S0:14 Eqs. (11) and (13) show that this quadratic has a double zero int.SinceB1cannotbeonlineL,(B12 S0) (S12 S0) 0; Fig. 3. Curve (1) tangent to the line segment S0S1at P. D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599593 dividing Eq. (14) by this non-zero quantity gives 1 2 t2A 2w1 2 tt t2C 0;15 where A B02 S0 S12 S0 B12 S0 S12 S0 ; C B22 S0 S12 S0 B12 S0 S12 S0 : 16 Thinking of A, w, and C as the y-values of a quadratic Be zier curve, and recalling that a positive value for w is required and thatadoublerootofEq.(15)isrequiredin(0,1),itmustbethat A , 0 and C , 0. The condition for a double root is w2 AC or w ffi ffi ffi ffi AC p :17 The double root occurs at t w 2 A 2w 2 A 2 C ;18 wherein the denominator is non-zero because w . 0, A , 0, and C , 0. Although this t-value is in (0,1), the point of tangencyP Bt;w;maynotbeinthelinesegmentS0S1,so a fi nal check is needed, namely, 0 , P 2 S0S12 S0 S12 S0S12 S0 , 1:19 A The above result is summarized in lemma 2. Lemma 2. If the Be zier control triangle B0B1B2has non- zero area, the infi nite line L that passes through the distinct points S0and S1does not cross B0B2, B1isnot on L, A and C in Eq. (16) are both negative, and Eq. (19) is satisfi ed, then there is a unique curve (1) tangent to the line segment S0S1. Otherwise, there is no curve (1) that is tangent to line segment S0S1. The w-, t-values at the point of tangency are givenin Eqs. (17) and (18),where Aand Care defi ned in Eq. (16). Result 5: The curve (1) that is tangent to a given circular arc. The w-value of the curve (1) that is tangent to a given arc can be found as described later. An arc will be specifi ed by two distinct endpoints S0and S1, and by a non-zero signed sweep angleufrom S0and S1(counterclockwise is positive). Let C be the circle of which the arc is a part. The procedure is fi rst to fi nd a curve (1) that is tangent to C, then test if the point of tangency is in the given arc (see Fig. 4). Ifuis positive, let U be the unit vector that is a rotation of p/2 from the direction S12 S0, while ifuis negative, let U be the unit vector that is a rotation of 2p/2 from the direction S12 S0. The centre E and radius r of circle C are E S0 S1 2 kS12 S0k 2 tan u 2 ? ? ? ? ? ? ? ? U;r kS12 S0k 2 sin u 2 ? ? ? ? ? ? ? ? : By analogy with Result 4, if a curve (1) is tangent to a circle center E and radius r, then the equation Bt;w 2 E?Bt;w 2 E? 2 r2 020 has a double root in t. Using Eq. (1), Eq. (20) becomes Qt;w 2 qt;wE?Qt;w 2 qt;wE? 2 r2qt;w?2 0: 21 The left hand side of Eq. (21) in Bernstein form is c01 2 t4 4c1w1 2 t3t 2c2 2c3w2?1 2 t2t2 4c4w1 2 tt3 c5t4;22 where c0 B02 EB02 E 2 r2; c1 B02 EB12 E 2 r2; c2 B02 EB22 E 2 r2; c3 B12 EB12 E 2 r2; c4 B12 EB22 E 2 r2; c5 B22 EB22 E 2 r2: Converting to power representation, polynomial (22) becomes a4t4 4a3t3 6a2t2 4a1t a023 where a4 4c3w22 4c1 c4w c0 2c2 c5; a3 22c3w2 3c1 c4w 2 c02 c2; a2 2 3 c3w22 2c1w c0 1 3 c2; a1 c1w 2 c0;a0 c0: Tangents occur when Eq. (23) has a double zero in t; a method for checking for a double zero is described in Appendix A. The condition for Eq. (23) to have a double Fig. 4. Curve (1) tangent to an arc from S0to S1at P. D.S. Meek et al. / Computer-Aided Design 35 (2003) 591599594 zero in t, D 0 where D is defi ned in the Appendix A, leads to an eighth degree polynomial equation of even powers in w. Here only positive w-values whose corresponding t- values are in (0,1) are acceptable. For each point of tangency to the circle, a check is made to see if the point is in the arc being considered. The result of this process is a set of possible w-values for curves (1) (the set may be empty). Note that a curve (1) may be tangent to the arc in two places and there may be several curves (1) tangent to the arc. Since the largest w-value will be taken later, this multiplicity of curves (1) does not cause any diffi culty. A Result 5 can be restated in the following lemma 3. Lemma 3. If the area of the Be zier control triangle B0B1B2 is non-zero, S0and S1are distinct endpoints of an arc, the sweep angle of the arcuis non-zero, there are positive w- values such that Eq. (21) has a double zero in t for t in (0,1), the points of tangency are in the arc from S0to S1,then there exist one or more curves (1) that are tangent to the arc from S0to S1. Otherwise, no curve (1) exists that is tangent to the arc from S0to S1. 3. A solution of the constrained curve drawing problem A solution to the constrained curve drawing problem presented in this section is based on a quadratic B-spline with uniform knots. In this section, assume that the B-spline control polyline does not intersect the constraining bound- ary. A typical segment of the quadratic B-spline control polyline has control points P0, P1, P2. The corresponding quadratic Be zier control points are: B0 P0 P1 2 ;B1 P1;B2 P1 P2 2 : If the control polyline of a quadratic B-spline is closed, then the control polyline of the corresponding quadratic Be zier curves follows the same path; if the control polyline of a quadratic B-spline is open, then the control polyline of the corresponding quadratic Be zier curves follows the same path, but is slightly shorter (at both ends). Thus, if the B- spline control polyline does not cut the boundary, then the corresponding Be zier control polyline does not cut the boundary. Henceforth, references will be to the Be zier control polyline and its corresponding Be zier curves rather than to the B-spline control polyline and curve. Further- more, each Be zier segment can be considered separately because overall G1continuity is guaranteed from the Be zier control polyline. Before discussing the algorithm, it is helpful to consider a default weight w, and to examine two simple cases. Whenever possible, a quadratic curve (parabola, w 1) will be used rather than a rational quadratic (conic, w 1). This default choice seems to give nice curves, although it is somewhat arbitrary and could be chosen differently. The choice w 1 does give the algebraically simplest curves. Even if a different choice were made, it would probably not be too far from 1. Fig. 5 shows the control polyline in gray and quadratic B-splines with three different weight values; the weight w 1 gives the nicest curve of the three. Case 1: (boundary does not enter the control triangle B0B1B2). Here, the control triangle is entirely on one side of the boundary (see Fig. 6). Since all the curves (1) are entirely inside the triangle B0B1B2,