Prof. Ligang Liu at USTC (中科大刘利刚教授).pdf

Computers & Graphics 36 (2012) 309–320 Contents lists available at SciVerse ScienceDirect Computers & Graphics journal homepage: www.elsevier.com/locate/cag SMI 2012: Full Paper Curve intersection using hybrid clipping$ Qi Lou, Ligang Liu n Department of Mathematics, Zhejiang University, Hangzhou 310027, China a r t i c l e i n f o abstract Article history: Received 2 December 2011 Received in revised form 15 March 2012 Accepted 17 March 2012 Available online 30 March 2012 This paper presents a novel approach, called hybrid clipping, for computing all intersections between two polynomial Bézier curves within a given parametric domain in the plane. Like Bézier clipping, we compute a ‘fat line’ (a region along a line) to bound one of the curves. Then we compute a ‘fat curve’ around the optimal low degree approximation curve to the other curve. By clipping the fat curve with the fat line, we obtain a new reduced subdomain enclosing the intersection. The clipping process proceeds iteratively and then a sequence of subdomains that is guaranteed to converge to the corresponding intersection will be obtained. We have proved that the hybrid clipping technique has at least a quadratic convergence rate. Experimental results have been presented to show the performance of the proposed approach with comparison with Bézier clipping. & 2012 Elsevier Ltd. All rights reserved. Keywords: Bézier curve Curve intersection Bézier clipping Hybrid clipping 1. Introduction Computing intersections of two curves has played an important role in many engineering fields, including computer-aided design and manufacturing (CAD/CAM), collision detection, and geometric modeling [1–3]. If the two curves are parametric, the solution is identified by the parameter values of intersection points. Early approaches include the Bézier subdivision algorithm [4], the interval subdivision method [5], and implicitization [6]. One widely used and robust method is Bézier clipping, which was developed by [7]. It utilizes the convex hull property of Bézier curves and proceeds as clipping away regions of the curves that are guaranteed to not intersect. Recently, [8] proved that Bézier clipping has a quadratic convergence rate. Bézier clipping can be applied to compute roots of polynomials as well. By extending Bézier clipping, [9] developed the quadratic clipping technique to compute all the roots of a univariate polynomial equation within an interval. The basic idea is to generate a strip bounded by two quadratic polynomials which encloses the original polynomial via degree reduction. Combined with subdivision, quadratic clipping generates a sequence of intervals that contain the roots of the original polynomial. Recently, [10] extended this technique to cubic clipping and more general cases. Theoretical and experimental results have shown $ If applicable, supplementary material from the author(s) will be available online after the conference. Please see http://dx.doi.org/10.1016/j.cag.2012.03. 021. n Corresponding author. Tel./fax: þ 86 571 87953668. E-mail address: ligangliu@zju.edu.cn (L. Liu). 0097-8493/$ - see front matter & 2012 Elsevier Ltd. All rights reserved. http://dx.doi.org/10.1016/j.cag.2012.03.021 that both quadratic clipping and cubic clipping have at least quadratic convergence rates. In many cases intersection algorithms involve numerical methods for solving systems of bivariate polynomial equations system [11]. Ref. [12] presented an algorithm for computing all roots of a given bivariate polynomial system within a given rectangular domain. They construct the best linear approximants to the polynomials and use them to define planar strips enclosing the roots. The work of [13] used one linear and one quadratic approximants to the two polynomials to improve the convergence rate. Recently, Mourrain and Pavone [14] presented an improvement of Interval Projected Polyhedron (IPP) algorithm [15] for solving a system of polynomials, which uses a reduction strategy based on univariate root finder and Descarte’s rule. Instead of extending Bézier clipping to solve roots of two polynomials, we develop a new technique, called hybrid clipping, to directly compute all the intersections between two Bézier curves within a given parametric domain. Like Bézier clipping, we first compute a linear strip to bound one of the curves. Second, we compute the best approximant with lower degree (e.g., quadratic or cubic) of the other curve and then compute a curved strip around this curve. By intersecting the linear strip and the curved strip, we obtain a new reduced subdomain that encloses the intersections. This algorithm is applied iteratively combined with bisection steps and a sequence of subdomains that converge to the corresponding intersections are obtained. We have proved that the convergence rate of the proposed hybrid clipping algorithm is at least quadratic which is as high as Bézier clipping and is in many cases better than Bézier clipping. This paper is organized as follows. After a brief review on the Bézier clipping algorithm, we describe the hybrid clipping algorithm in Section 2. Section 3 gives the convergence rate theorem 310 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 and its proof. Section 4 provides some experimental results on comparisons with Bézier clipping. We conclude the paper with future work in Section 5. 2. Computing curve intersection via hybrid clipping In this section, we first review the Bézier clipping algorithm and then introduce our hybrid clipping algorithm for computing the intersections between two polynomial Bézier curves. 2.1. Review on Bézier clipping for curve intersection Let Pn½a, b be the linear space of planar polynomial Bézier curves of degree n within ½a, b. Any Bézier curve fðtÞ A Pn½a, b can be represented by its Bernstein–Bézier (BB) representation as fðtÞ ¼ n X ai Bni,½a, b ðtÞ, t A ½a, b, on degree reduction have higher convergence rates than Bézier clipping, which make the intersection computation much faster. Inspired from these works, we propose a new approach for computing the intersections between two polynomial Bézier curves f and g based on degree reduction. As in Bézier clipping, we use a fat line (linear strip) L to bound one of the curves, say, g. We then compute a curved strip P, called fat curve, which is enclosed by two polynomial Bézier curves with low degrees, say, quadratic or cubic, around the other curve f. By intersecting the two strips L and P, which can efficiently be computed in closed forms, we can compute a reduced subdomain that includes the intersection, see Fig. 1. As we use both a linear strip and a curved strip to bound the intersection, we call this approach hybrid clipping. The hybrid clipping algorithm for computing the intersections between two polynomial Bézier curves is given in Table 1. We will ð1Þ i¼0 where Bni,½a, b ðtÞ ¼ n ðtaÞi ðbtÞni i ðbaÞn , i ¼ 0; 1, . . . ,n ð2Þ are the Bernstein basis with degree n in ½a, b and ai A R2 ði ¼ 0; 1, . . . ,nÞ are the control points of this curve [2]. Bézier clipping was developed by [7] to compute the intersections between two polynomial Bézier curves fðtÞ in (1) and P m gðsÞ ¼ m i ¼ 0 bi Bi,½x, Z ðsÞ within the parameter domain ½a, b  ½x, Z, which is an iterative method by taking advantages of the convex hull property of Bézier curve. First, it computes a ‘fat line’, which is defined as the region between two parallel lines, to bound one of the two curves, say, fðtÞ. Then it clips away regions of the second curve gðsÞ, which are guaranteed to not intersect the fat line, by computing the distance function of g to the fat line. Similarly f is then clipped by a fat line around g. This intersection algorithm proceeds by iteratively applying the clipping procedure and generates a sequence of parameter subdomains ½ai , bi   ½xi , Zi , i ¼ 1; 2, . . . , which might contain an intersection of these two curves. The lengths of these intervals decrease to zero and the interval with maximum length which is less than e is returned to locate the intersection, where e specifies the desired accuracy. Bézier clipping performs much better than the classical Newton’s method for computing the curve intersections. It does not require a suitable initial guess and is guaranteed to find all intersections in a given domain. And it converges more robustly than Newton’s method. Recently, [8] proved that Bézier clipping has a quadratic convergence rate at transversal intersection, the equivalent of single root of function. In the case of tangent intersections, the equivalent of multiple root of function, however, only linear convergence was observed. Fig. 1. Illustration of hybrid clipping for intersecting two curves f and g. The curve g is bounded by a fat line L (the linear strip in light gray). A fat curve (the curved strip in dark gray) P is computed around the curve f. The intersection between f and g is bounded by the intersection between two strips L and P. Table 1 Hybrid clipping algorithm for computing intersections between two polynomial Bézier curves f and g within the domain ½a, b  ½x, Z. Algorithm 1 HybridClip ðf,g,½a, b,½x, Z,kÞ if maxðba, ZxÞ Z e then if ba Z Zx then L’ compute the fat line of g P’ compute the fat curve of f if the fat curve P doesn’t intersect the fat line L within ½a, b then return (|) else Find intervals ½ai , bi , i ¼ 1, . . . ,l, by intersecting P with L if maxi ¼ 1,...,l 9ai bi 9Z 129ab9 then return HybridClip (f,g, ½a, 12 ða þ bÞ,½x, 12ðx þ ZÞ,k) 2.2. Hybrid clipping algorithm for curve intersection As we see, Bézier clipping needs to compute the intersections between a line and a polynomial Bézier curve in each of its iteration, which can be converted into a root-finding problem for polynomial equation. Recently, the works of [9,10] proposed efficient approaches, which extended Bézier clipping, for computing the roots of a polynomial. The basic idea is to use a polynomial with low degree, say 2 or 3, to approximate the original polynomial based on degree reduction. Then two polynomials with low degrees are obtained to bound the original polynomial and their roots bound the corresponding roots of the original polynomial. These approaches are pretty efficient due to the fact that the roots for quadratic or cubic polynomials can be computed analytically. As shown in [9,10], these clipping approaches based {Hybrid clipping} [ HybridClip(f,g, ½a, 12 ða þ bÞ,½12ðx þ ZÞ, Z,k) [ HybridClip(f,g, ½12 ða þ bÞ, b,½x, 12ðx þ ZÞ,k) [ HybridClip(f,g, ½12 ða þ bÞ, b,½12ðx þ ZÞ, Z,k) else S’| for i ¼ 1, . . . ,l do S’S[ HybridClip(f,g,½ai , bi ,½x, Z,k) end for return (S) end if end if else return HybridClip ðg,f,½x, Z,½a, b,kÞ else return (½a, b,½x, Z) end if Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 give detailed explanation about this algorithm in the following sections. 311 Thus we have   n n X  X   n JfðtÞpðtÞJ ¼  ðai ci ÞBi,½a, b ðtÞ r Jai ci JBni,½a, b ðtÞ r d:   i¼0 2.3. Fat curve construction via degree reduction The fat line of gðsÞ is constructed as in Bézier clipping [7], which is constructed by two lines that are parallel to the chord of g, see Fig. 2. We now introduce the construction of fat curve for fðtÞ based on degree reduction. Denote J  J as the canonical Euclidean norm of fðtÞ A R2 . We define three other norms in Pn½a, b as follows: 1. normalized L2 norm: 1 JfJ2½a, b ¼ pffiffiffiffiffiffiffiffiffiffi Z b ba a !1=2 2 JfðtÞJ dt , ð3Þ 2. L1 norm: ð9Þ i¼0 We offset pðtÞ along a unit vector nðtÞ by the distance d and get two curves as p1 ðtÞ ¼ pðtÞ þ dnðtÞ, p2 ðtÞ ¼ pðtÞdnðtÞ: ð10Þ It can be seen by the definition of BB norm that fðtÞ lies between p1 ðtÞ and p2 ðtÞ on the line segment. That is, fðtÞ is ‘bounded’ by the two curves p1 ðtÞ and p2 ðtÞ along the direction of nðtÞ at each t. We call p1 ðtÞ and p2 ðtÞ the upper bound and the lower bound of fðtÞ along n respectively. The unit vector n in (10) should be carefully chosen in order to ease the analysis of convergence rate of our proposed hybrid clipping algorithm. In our algorithm, we set n as the unit vector that is perpendicular to the chord ðbm b0 Þ of gðsÞ, see Fig. 2. Denote dmax ¼ max ðn  ðbi b0 ÞÞ, i ¼ 0,...,m ½a, b JfJ1 ¼ max JfðtÞJ, t A ½a, b ð4Þ dmin ¼ min ðn  ðbi b0 ÞÞ, ð11Þ dðtÞ ¼ n  ðfðtÞb0 Þ, ð12Þ i ¼ 0,...,m 3. BB norm: ½a, b JfJBB ¼ max Jai J: d0 ðtÞ ¼ n  ðpðtÞb0 Þ, ð5Þ i ¼ 0,...,n d1 ðtÞ ¼ n  ðp1 ðtÞb0 Þ ¼ d0 ðtÞ þ d, It is easy to verify that the above norms are invariant under affine transformations of the t-axis [9]. Specifically, each of the three norms can be regarded as a functional F ½a, b defined in Pn½a, b . Then given any affine transformation A : t/A0 þ A1 t, ð6Þ with A1 a 0, the following equation holds: F ½a, b ðfÞ ¼ F Að½a, bÞ ðf JA1 Þ: d2 ðtÞ ¼ n  ðp2 ðtÞb0 Þ ¼ d0 ðtÞd: ð13Þ Then we have 9dðtÞd0 ðtÞ9 ¼ 9n  ðfðtÞpðtÞÞ9 rJnJ  JfðtÞpðtÞJ ¼ JfðtÞpðtÞJ ½a, b rJfðtÞpðtÞJ1 r d, ð14Þ which means that d(t) is enclosed in the strip bounded by d1 ðtÞ and d2 ðtÞ, see Fig. 3. We summarize the algorithm for computing the fat curve P of f in Table 2. ð7Þ Let pðtÞ A Pk½a, b with k on be the optimal L2 approximation to fðtÞ A Pn½a, b . As shown in Appendix A, pðtÞ can be obtained using the degree reduction technique, which can easily be computed by matrix computation. We represent pðtÞ as a degree n curve P pðtÞ ¼ ni¼ 0 ci Bni,½a, b A Pn½a, b by degree elevation (see Appendix B) and denote a, b d ¼ JfðtÞpðtÞJ½BB : 2δ d max d1(t ) α ð8Þ β d (t ) d min d 2 (t ) Fig. 3. Computation of the subintervals which bounds the intersections. b1 b3 g( s ) b0 b2 p1(t ) f (t ) p 2 (t ) Fig. 2. Illustration of fat line and fat curve. The fat line of gðsÞ is bounded by two lines that are parallel to the chord of its control polygon. The fat curve of fðtÞ is bounded by two curves p1 ðtÞ and p2 ðtÞ with lower degrees. Table 2 Compute the fat curve of f via degree reduction. Algorithm 2 ComputeFatCurve ðf,g,kÞ p’ generate a degree k curve of f by degree reduction ½a, b d’ compute JfpJBB n’ compute a unit vector that is orthogonal to ðbm b0 Þ of gðsÞ p1 ’p þ dn {upper bound} p2 ’pdn {lower bound} return P ¼ ðp1 ,p2 Þ {Fat curve} Fig. 4. Proof of Eq. (15). [6,7] 2.574 [4,4] 1.747 [4,5] 1.606 [5,6] 2.168 [3,4] 1.528 [4,4] 1.435 [4,5] 1.747 [3,3] 1.263 [3,4] 1.248 [4,4] 1.575 [2,3] 1.076 [3,3] 1.060 [3,3] 1.170 [2,3] 0.858 ½Nf ,Ng  t [2,2] 0.873 [5,12] 10.514 [3,10] 12.760 [4,10] 9.266 [4,11] 10.218 [3,9] 12.604 [3,10] 9.157 [3,10] 9.843 [2,9] 12.480 [2,9] 8.751 [2,9] 9.516 [1,8] 12.136 [2,8] 8.704 [1,8] 9.250 [1,8] 11.965 [4,4] 0.998 [4,5] 0.748 [5,5] 0.920 [3,4] 0.858 [4,4] 0.702 [4,4] 0.764 [3,3] 0.748 [3,3] 0.514 [3,3] 0.561 [2,2] 0.499 [3,3] 0.514 BezClip 3-HybClip BezClip [2,2] 0.374 3-HybClip BezClip 2-HybClip 3-HybClip BezClip 1064 1032 1016 (8,8) Li +1 li +1,3 [1,8] 8.580 li +1,2 ½Nf ,Ng  t li +1,1 (8,4) d (t ) d 2 (t ) [2,2] 0.327 d1 (t ) slope ω4 ½Nf ,Ng  t βi +1 slope ω4 βi (4,4) αi +1 2-HybClip αi 3-HybClip 2δi 2-HybClip Definition 3.1. Suppose that fðtÞ A Pn½a, b and gðsÞ A Pm ½x, Z intersect at z0 ¼ fðt 0 Þ ¼ gðs0 Þ, where t 0 A ½a, b and s0 A ½x, Z. The intersection 0 z0 is called a transversal intersection if f ðt 0 Þ  g0 ðs0 Þ a 0; z0 is 108 We give the convergence rate of the proposed hybrid clipping algorithm in this section. 104 3. Convergence rate of hybrid clipping e HybridClipðf,g,½a, b,½x, Z,kÞ will return some pairs of intervals containing all the intersections of f and g within ½a, b  ½x, Z given a prescribed tolerance e. This technique guarantees to find all the intersections of two planar Bézier curves within a given domain. However, like Bézier clipping, the approach may produce false positive answers (i.e., some pairs of intervals do not contain any intersection) if the two curves get too close to each other. Degrees (n,m) Algorithm 2. Note that the fat curve P only bounds f along some direction at each point. The region of P does not necessarily enclose the curve of f.  In line 1 of Algorithm 2, when we utilize Eq. (A.1) to compute the best approximation of degree k, all the matrices involved can be precomputed and stored in a lookup-table to save time. Similarly, we precompute and store the matrices for degree elevation given in Eq. (B.1).  In line 8 of Algorithm 1, after discarding those intervals that satisfy d1 ðtÞ o dmin or d2 ðtÞ 4 dmax , we obtain a series of closed intervals ½ai , bi , i ¼ 1, . . . ,l, that bound the intersections, see Fig. 3.  It is obvious that ko minðn,mÞ. Practically we choose k¼2 or 3 as the roots of quadratic and cubic polynomials can be analytically calculated [10].  In line 3 of Algorithm 1, we compute the fat line as in [7]. Actually, any pair of parallel lines that bound the curve can serve as a fat line. Other fat line construction methods were discussed in [8].  In our practical implementation, we always use the fat line of the curve with smaller interval to clip the fat curve of the other curve, which will make the algorithm more efficiently, see line 20 of Algorithm 1. Table 3 Example 1 (transversal intersections): number pairs of iterations ½Nf ,Ng  and computing times t in seconds for various values of accuracy e. (n,m) are degrees of the two curves f,g, respectively.  In line 4 of Algorithm 1, the fat curve P of f is computed by 2-HybClip 3-HybClip Some steps of Algorithms 1 and 2 will be explained in more detail in the following: [2,2] 0.499 BezClip 2.4. Remarks on the algorithms [6,6] 1.092 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 2-HybClip 312 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 0 313 called a tangent intersection if f ðt 0 Þ  g0 ðs0 Þ ¼ 0 and 0 f ðt 0 Þ a0, g0 ðs0 Þ a0; z0 is called a degenerate intersection 0 if one of the curves has no tangent at z0 , i.e., f ðt 0 Þ ¼ 0 or g0 ðs0 Þ ¼ 0. We will prove this convergence rate theorem based on two technical lemmas which respectively can be regarded as the ‘vector versions’ of Lemmas 1 and 2 in [10]. In order to make this paper selfcontained, we give these two technical lemmas and their proofs first. The following theorem gives the convergence rates of the hybrid clipping approach for transversal intersections. Lemma 3.3. Given a planar Bézier curve f of degree n, there exists a constant C 0f depending solely on f, such that for all intervals kþ1 ½a, b D½0; 1 the bound d in (8) satisfies d r C 0f h , where h ¼ ba. Theorem 3.2. Suppose fðtÞ A Pn½a, b and gðsÞ A Pm ½x, Z have a transversal intersection z0 ¼ fðt 0 Þ ¼ gðs0 Þ. Furthermore, suppose ð½ai , bi Þi ¼ 0; 1,2, . . . is the sequence of generated intervals that contain t0, and ð½xi , Zi Þi ¼ 0;1,2,... is the corresponding sequence of generated intervals that contain s0, then there exist constants C f depending solely on f and C g depending solely on g, such that for sufficiently large i A N, the following inequality holds: kþ1 hi þ 1,f rC f hi,f 2 þ C g hi,g , Proof. Due to the equivalence of norms in finite-dimensional real linear spaces, there exist constants C1, C2 such that ½a, b r C 1 JrJ2½a, b JrJBB ½a, b JrJ2½a, b rC 2 JrJ1 ð17Þ for all r A Pn½a, b . The constants C1 and C2 do not depend on the given interval ½a, b, since all the norms are invariant with respect to affine transformations of the t-axis. Therefore ð15Þ ½a, b ½a, b d ¼ JfpJBB r C 1 JfpJ2½a, b r C 1 Jfqa J2½a, b r C 1 C 2 Jfqa J1 where hi,f ¼ bi ai and hi,g ¼ Zi xi . Similarly, there exist constants C 0f depending solely on f and C 0g depending solely on g, such that for sufficiently large i A N, the following inequality holds: 2 kþ1 hi þ 1,g rC 0f hi,f þ C 0g hi,g : and pffiffiffi 2 ðk þ 1Þ kþ1 C 1 C 2 max Jf r ðt 0 ÞJh , ðk þ1Þ! t A ½0;1 ð18Þ where each of the components of qa is the degree k Taylor polynomials at t ¼ a to the corresponding component of f and ðk þ 1Þ f is the ðk þ1Þ-th derivative vector. & ð16Þ 80 t 60 1 40 0.9 20 0.8 f 0 0.7 −20 0.6 −40 0.5 g −60 3−HybClip BezClip 2−HybClip 0.4 −80 −80 −60 −40 −20 0 20 2 40 40 12.5 30 20 3 log log(1/ε) 6 5 log log(1/ε) 6 2 3−HybClip 11.5 0 5 t 12 f 10 4 11 −10 BezClip 10.5 −20 −30 g 10 −40 9.5 −50 2−HybClip 9 −60 −70 −40 −30 −20 −10 0 10 20 30 2 3 4 2 4 3 x 10 2.5 t 2.5 2 2 1.5 BezClip 1 0.5 f 3−HybClip 1.5 0 −0.5 −1.5 -1.5 2−HybClip g −1 1 -1 -0.5 0 0.5 1 1.5 x 10 2 3 4 5 log log(1/ε) 2 6 4 Fig. 5. Example 1 (transversal intersections). Left: the figures of the curve pairs; right: computing time t in seconds vs. accuracy. The degrees (n,m) of the two curves are (4,4) (upper row), (8,4) (middle row), (8,8) (lower row), respectively. ð25Þ Thus there exists e3 40 such that 0 9d ðtÞd01 ðtÞ9 o o=4 ð26Þ as hi,f o e3 . Let e4 ¼ minðe1 , e2 , e3 Þ. By (23) and (24) we have 0 0 0 9d ðtÞo9 ¼ 9n  f ðtÞn0  f ðt 0 Þ9 0 0 0 0 r 9n  f ðtÞn  f ðt 0 Þ9 þ9n  f ðt 0 Þn0  f ðt 0 Þ9 0 0 0 r Jf ðtÞf ðt 0 ÞJ þ 9d ðt 0 Þo9 o o=4 þ o=4 ¼ o=2 ð27Þ 0 as hi,g o e4 , hi,f o e4 . Thus d ðtÞ 4 o=2. By (26) we know d01 ðtÞ ¼ d02 ðtÞ 4 o=4: ð28Þ From Fig. 4 we have the bound for hi þ 1,f as hi þ 1,f rLi þ 1 ¼ li þ 1;1 þli þ 1;2 þli þ 1;3 : ð29Þ [151,136] 295.543 [113,107] 212.457 [117,103] 185.063 [73,73] 108.685 [58,51] 86.159 [61,49] 76.112 [34,39] 48.781 [28,28] 39.827 [31,25] 33.462 [16,20] 24.819 [0,213] 243.907 [0,213] 334.700 [0,213] 225.327 [0,107] 95.020 [0,107] 136.142 [0,107] 100.293 [0,54] 43.820 [0,54] 60.699 [111,73] 61.058 [110,79] 46.441 [0,107] 79.248 BezClip 1064 3-HybClip [56,38] 29.203 [54,43] 23.961 [0,54] 37.596 [28,18] 13.930 [28,22] 11.996 [0,54] 43.227 [0,27] 20.498 [0,27] 29.686 [16,14] 21.169 [15,13] 17.518 [10,9] 12.495 0 [5,8] 9.796 k ½a, b rJf ðtÞp0 ðtÞJ1 r C 2f hi,f : [7,6] 7.831 0 ½Nf ,Ng  t 0 (8,8) 0 9d ðtÞd01 ðtÞ9 ¼ 9n  ðf ðtÞp0 ðtÞÞ9 r Jf ðtÞp0 ðtÞJ [0,27] 19.250 as hi,f o e2 . By Lemma 3.4 we have [0,14] 10.062 ð24Þ [0,14] 14.336 0 [0,14] 9.656 0 Jf ðtÞf ðt 0 ÞJ o o=4 ½Nf ,Ng  t as hi,g o e1 . 0 Due to the continuity of f ðtÞ, there exists e2 4 0 such that (8,4) ð23Þ [4,8] 4.212 0 ½Nf ,Ng  t 0 (4,4) 0 9d ðt 0 Þo9 ¼ 9n  f ðt 0 Þn0  f ðt 0 Þ9 o o=4 BezClip Proof (Proof of Theorem 3.2). Note that f and g play the same role in the algorithm. We only prove (15) here. It is observed that the length of intervals ½ai , bi  tends to be 0 as i tends to infinity, since subdivision is introduced in the algorithm (see line 10 of Algorithm 1). The chord b0 bm of g tends to the tangent line at z0 when the length of the interval ½xi , Zi  tends to be 0. Therefore, the unit vector n (see line 3 of Algorithm 2) tends to the unit normal vector n0 of g at z0 . 0 0 Denote o ¼ n0  f ðt 0 Þ. As f ðt 0 Þ  g0 ðs0 Þ a0, then o a 0. Without loss of generality, we assume o 40 (otherwise we can take n instead of n and n0 instead of n0 Þ. Since n0 is the limit of n, there exists e1 40 such that 3-HybClip here qa has the same meaning as that in the proof of (3.3). Clearly, this implies (19). & BezClip ð22Þ 3-HybClip pffiffiffi 2 ðk þ 1Þ kþ1 C 2 C 3 max Jf r ðt 0 ÞJh , ðkþ 1Þ! t A ½0;1 2-HybClip ðkÞ BezClip 0 ½a, b r C 3 JfpJ2½a, b r C 3 Jfqa J2½a, b rC 2 C 3 Jfqa J1 3-HybClip k ½a, b ½a, b ½a, b þ hJf p0 J1 þ    þ h Jf pðkÞ J1 JfpJ½na, b ¼ JfpJ1 2-HybClip Consequently, 1032 ð21Þ 1016 JrJ½na, b r C 3 JrJ2½a, b : 108 Due to the affine invariance of the norms, there exists a constant C3, which does not depend on the interval ½a, b, such that ([9]) 104 ð20Þ e k a, b ½a, b a, b þhJr0 J1 þ    þ h JrðkÞ J½1 : JrJ½na, b ¼ JrJ½1 Degrees (n,m) Proof. We construct a new norm in ½a, b as Table 4 Example 2 (tangent intersections): number pairs of iterations ½Nf ,Ng  and computing times t in seconds for various values of accuracy e. (n,m) are degrees of the two curves f,g, respectively. with h ¼ ba. [0,27] 18.548 ð19Þ [15,8] 6.770 ðkÞ [10,13] 7.066 ½a, b rC ðk þ 1Þf h, Jf pðkÞ J1 [0,14] 9.516 0 [7,5] 3.182 3-HybClip k a, b Jf p0 J½1 rC 2f h , . . . , , 2-HybClip kþ1 2-HybClip ½a, b rC 1f h JfpJ1 BezClip Lemma 3.4. Given a planar Bézier curve f of degree n, there exist k þ1 constants C 1f ,C 2f , . . . ,C ðk þ 1Þf , depending solely on f, such that for all intervals ½a, b D ½0; 1 the optimal approximate curve p of degree k to f satisfies [0,213] 180.524 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 2-HybClip 314 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 Let pðtÞ ¼ ðxðtÞ,yðtÞÞ. There exist tn and t between t1 and t2 such that First it is seen that li þ 1;1 þli þ 1;3 ¼ 315 % dmax dmin 4ðdmax dmin Þ ¼ : o=4 o ð30Þ pðt 1 Þpðt 2 Þ ¼ ðxðt 1 Þxðt 2 Þ,yðt 1 Þyðt 2 ÞÞ ¼ ðx0 ðt n Þðt 1 t 2 Þ,y0 ðt Þðt 1 t 2 ÞÞ: ð34Þ % Thus we have Now we try to obtain an upper bound for li þ 1;2 . As d01 ðtÞ ¼ d02 ðtÞ 4 o=4 40, both functions d1 ðtÞ and d2 ðtÞ strictly increase in the interval ½ai , bi . Therefore, for any y0 such that d1 ðai Þ oy0 o d2 ðbi Þ, the following two equations have roots t 1 ,t 2 within the interval ½ai , bi  % 0 0 ¼ 9n  ðx0 ðt n Þ,y0 ðt ÞÞn  f ðtÞ9 rJðx0 ðt n Þ,y0 ðt ÞÞf ðtÞJ % % 0 ¼ Jðx0 ðt n Þ,y0 ðt n ÞÞf ðtÞ þ ð0,y0 ðt ÞÞð0,y0 ðt n ÞÞJ 0 % r Jp ðt Þf ðtÞJ þ Jp ðt Þp ðt ÞJ 0 d1 ðtÞ ¼ y0 , n 0 0 % n 0 r Jp0 ðt n Þp0 ðtÞJ þ Jp0 ðtÞf ðtÞJ þJp0 ðt Þp0 ðt n ÞJ d2 ðtÞ ¼ y0 : r2 f9t 1 t 2 9 : d1 ðt 1 Þ ¼ d2 ðt 2 Þ ¼ y0 g, sup ½ai , bi  Jp0 ðt 1 Þp0 ðt 2 ÞJ þJp0 ðtÞf ðtÞJ1 : ð35Þ By Lemma 3.4 and the fact that p0 ðtÞ is uniformly continuous in ½ai , bi , there exists e5 4 0 such that ð32Þ y0 A ðd1 ðai Þ,d2 ðbi ÞÞ max t1 ,t2 A ½ai , bi  where t 1 ,t 2 A ½ai , bi . As d1 ðt 1 Þ ¼ d2 ðt 2 Þ ¼ y0 , we have n  ðpðt 1 Þpðt 2 ÞÞ ¼ 2di , % 0 max t1 ,t2 A ½ai , bi  ð31Þ Obviously li þ 1;2 r 0 9n  ðx0 ðt n Þ,y0 ðt ÞÞd ðtÞ9 Jp0 ðt 1 Þp0 ðt 2 ÞJ o o=16, ½ai , bi  o o=8 Jp0 f J1 0 ð33Þ ð36Þ as hi,f o e5 . where di is computed as the corresponding one in (8). 4.5 180 4 160 3.5 t 140 3 2.5 120 2 100 1.5 80 1 0.5 f 0 BezClip 60 g 3−HybClip 40 2−HybClip 20 −0.5 −1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 2 4 3 4 5 t 6 3−HybClip 300 3 log2log(1/ε) 250 2 1 0 BezClip 200 g 150 f −1 2−HybClip 100 −2 50 −3 -3.5 -3 -2 -2.5 -1.5 -1 -0.5 0.5 0 1 2 3 4 5 t 2 200 g 0 f 6 BezClip 250 1 log2log(1/ε) 3−HybClip 150 −1 100 2−HybClip −2 50 −3 -3.5 -3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2 3 4 5 log log(1/ε) 2 6 Fig. 6. Example 2 (tangent intersections). Left: the figures of the curve pairs; right: computing time t in seconds vs. accuracy. The degrees (n,m) of the two curves are (4,4) (upper row), (8,4) (middle row), (8,8) (lower row), respectively. [135,8] 37.658 [9,10] 6.474 [13,11] 4.352 [68,7] 17.160 [8,9] 5.850 [11,9] 3.588 [34,6] 8.346 [7,6] 2.652 [8,7] 2.683 [17,5] 4.305 [5,5] 1.903 [6,5] 1.887 [9,4] 2.511 [4,4] 1.357 ½Nf ,Ng  t (8,8) [4,3] 1.341 [115,126] 63.601 [7,15] 10.810 [9,15] 6.271 [51,68] 34.164 [6,14] 10.374 [7,13] 5.647 [25,36] 21.512 [4,12] 8.782 [5,11] 5.132 [12,21] 14.430 [3,9] 7.035 [4,10] 4.820 [4,12] 11.918 [3,8] 4.383 [2,8] 6.708 [10,15] 6.786 [11,13] 4.804 [76,76] 27.518 [8,12] 5.584 [9,12] 4.570 [33,33] 11.746 [7,11] 5.132 [7,10] 4.180 [16,19] 6.848 [6,8] 4.024 BezClip ½Nf ,Ng  t In this section, we will do various numerical experiments to illustrate the performance of our proposed hybrid clipping (HybClip for short) technique and make comparisons with the classic Bézier clipping (BezClip for short) technique. From Theorem 3.2 we can see that HybClip has at least a quadratic convergence rate while BezClip has only a quadratic convergence rate [8]. As in [9,10] we introduce a few criteria, such as convergence rate, number of operations per iteration step, time per iteration step, number of iterations, and computing time needed to achieve a certain prescribed accuracy, to make an intensive comparison between these two techniques numerically. We had done a great number of experiments and the results had shown that HybClip performs better than BezClip in all these criteria. In order to make our manuscript more compact, here we show the experimental results based on a couple of criteria, that is, number of iterations and computing time needed to achieve a certain prescribed accuracy for convenience, to compare two techniques. Note that we can use different value of k to construct the fat curve for fðtÞ in Algorithm 1. That means we use an optimal (8,4) 4. Experimental results [6,8] 3.931 The key of the proof is introducing Li þ 1 to bound bi þ 1 ai þ 1 . Meanwhile, Li þ 1 can be decomposed into three components, i.e., li þ 1;1 , li þ 1;2 , and li þ 1;3 , each of which can be bounded separately. On one hand, the bound of li þ 1;2 relies on the estimation of the difference between the roots of d1 ðtÞ and d2 ðtÞ. On the other hand, li þ 1;1 þ li þ 1;3 can be computed directly. Note that the property that o is nonzero plays a crucial role in the construction of li þ 1;1 and li þ 1;3 . That is why transversal intersection is required in this proof. Due to this theorem, we conclude that the process of subdivision would not exist when intervals are sufficiently small, i.e., hybrid clipping indeed has the convergence rate of at least order 2, which is at least as high a convergence rate as that of Bézier clipping. Note that we have proved the convergence rates for computing the transversal intersections. But unfortunately we could not obtain the convergence rates for the case of tangent intersection where two curves are tangent at the intersection. As pointed in Bézier clipping [7], a large number of subdivisions may be needed and the algorithm tends to degenerate to a divide-and-conquer binary search for the cases of tangent intersections. [7,11] 4.773 kþ1 Clearly, this implies (15) from di r C 0f hi,f (see Lemma 3.3) and 2 dmax dmin r C 0g hi,g (see the proof of Theorem 6 of [8]). & ½Nf ,Ng  t ð40Þ (4,4) : 3-HybClip o BezClip 4ðdmax dmin Þ 3-HybClip þ BezClip o 3-HybClip 8di 2-HybClip hi þ 1,f rLi þ 1 o BezClip From (30) and (32), the above inequality implies 3-HybClip ð39Þ 2-HybClip : 1064 o 1032 8di 1016 ¼ 108 2di o=4 104 9t 1 t 2 9o e % Degrees (n,m) Since 2di ¼ n  ðpðt 1 Þpðt 2 ÞÞ ¼ ðt 1 t 2 Þn  ðx0 ðt n Þ,y0 ðt ÞÞ, we have Table 5 Example 3 (degenerate intersections): number pairs of iterations ½Nf ,Ng  and computing times t in seconds for various values of accuracy e. (n,m) are degrees of the two curves f,g, respectively. ð38Þ % [6,7] 3.775 n  ðx0 ðt n Þ,y0 ðt ÞÞ 4 o=4: 3-HybClip as hi,g o e0 and hi,f o e0 . Combining the above inequalities and (27), we have [4,6] 3.588 ð37Þ 2-HybClip % 2-HybClip 0 9n  ðx0 ðt n Þ,y0 ðt ÞÞd ðtÞ9 o o=4 BezClip Let e0 ¼ minðe4 , e5 Þ. Then we have [156,162] 53.461 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 2-HybClip 316 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 317 Bézier curves ( fðtÞ ¼ ððt1=3Þðt3Þðt þ 6Þ2 , ðt1=3Þðt þ 3Þðt6Þ2 Þ, degree k Bézier curve to approximate fðtÞ and then the algorithm involves computing the roots of degree k polynomials. By Theorem 3.2 we know that the larger k is, the faster the convergence rate is. To make the computation practically usable, we generally set k as 2 or 3 because the roots for quadratic or cubic polynomials are easy to compute. We set k¼2,3 in the following comparisons. And we refer 2-HybClip and 3-HybClip as HybClip with k¼2 and k¼3, respectively, for short. We have implemented all the algorithms on a PC with Intel(R) Core(TM) Duo CPU (2.00 GHz) with 2 GB of RAM and utilize Maple V12 to do all experiments with 600 significant digits. In these experiments, both curves fðtÞ and gðsÞ have the parameter domain ½0; 1. ( ( gðsÞ ¼ ððs1=3Þðs2Þðs þ 6Þ2 , ðs1=3Þðs3Þðs þ 6Þ2 Þ, fðtÞ ¼ ððt1=3Þðt3Þ3 ðt þ 6Þ4 , ðt1=3Þðt þ 3Þ3 ðt6Þ4 Þ, gðsÞ ¼ ððs1=3Þðs2Þðs þ 6Þ2 , ðs1=3Þðs3Þðs þ 6Þ2 Þ, fðtÞ ¼ ððt1=3Þðt3Þ3 ðt þ 6Þ4 , ðt1=3Þðt þ 3Þ3 ðt6Þ4 Þ, gðsÞ ¼ ððs1=3Þðs2Þ3 ðsþ 6Þ4 , ðs1=3Þðs3Þ3 ðs þ 6Þ4 Þ: Table 3 reports the number pairs of iterations ½Nf ,Ng  and the computing times in seconds for various values of desired accuracy e for computing the transversal intersections between the three pairs of Bézier curves with various degrees (n,m). As pointed out in Section 2.4, we always use the fat line of the curve with smaller interval to clip the fat curve of the other curve in 2-HybClip and 3-HybClip, like in BezClip. In both algorithms, the number Nf denotes the number of using the fat line of g to clip f (in BezClip) or the fat curve of f (in 2-HybClip or 3-HybClip). The same for the number Ng . Fig. 5 visualizes the relation between computing times and desired accuracy. 4.1. Single intersections We first show experimental results on computing the single intersections between two curves. The cases of transversal intersections are shown as follows. Example 1 (Transversal intersection). We applied the algorithms 2-HybClip, 3-HybClip, and BezClip to the three pairs of 3 50 2 t 45 1 40 0 35 −1 30 f −2 g −3 25 20 −4 BezClip 15 −5 10 −6 3−HybClip 5 −7 −5 −4 −3 −2 −1 0 1 2 2 0.2 60 0 −0.2 f −0.4 ~ 3 4 2−HybClip log2log(1/ε) 5 6 t 50 −0.6 40 −0.8 g −1 30 −1.2 BezClip 20 −1.4 −1.6 3−HybClip 10 −1.8 −0.2 0 0.2 0.4 0.8 0.6 1 1.2 1.4 2 20 35 10 0 f −10 ~ 3 4 2−HybClip 5 log log(1/ε) 2 6 t 30 25 −20 −30 20 −40 −50 BezClip 15 g −60 10 −70 3−HybClip 5 −80 −90 −2 0 2 4 6 8 10 12 2 3 4 2−HybClip log log(1/ε) 2 5 6 Fig. 7. Example 3 (degenerate intersections). Left: the figures of the curve pairs; right: computing time t in seconds vs. accuracy. The degrees (n,m) of the two curves are (4,4) (upper row), (8,4) (middle row), (8,8) (lower row), respectively. ððt1=3Þ2 ðt2Þ2 ðt þ 3Þ4 , ðt1=3Þ2 ðt þ 1Þ5 ðt4ÞÞ, gðsÞ ¼ ððs1=3Þ2 ðs2Þ2 ðs þ 1Þ4 , ðs1=3Þðs3Þ3 ðs þ1Þ4 Þ: Table 5 reports the number pairs of iterations ½Nf ,Ng  and the computing times in seconds for various values of desired accuracy e for computing the tangent intersections between the three pairs of Bézier curves with various degrees (n,m). Fig. 7 visualizes the relation between computing times and desired accuracy. We can see that both 2-HybClip and 3-HybClip perform much better than BezClip for computing the degenerate intersections between curves. Unfortunately, we are not able to give the exact convergence rate in theory for these cases. [49,79] 38.969 [33,56] 22.214 [40,65] 22.604 [41,71] 35.115 [30,51] 20.436 [36,58] 20.576 [34,63] 31.418 [25,48] 18.564 [30,52] 18.220 [26,55] 28.002 [22,43] 16.676 [27,37] 10.670 [17,26] 7.659 [20,31] 8.299 [23,33] 9.547 [16,23] 6.910 [18,28] 7.612 [19,29] 8.392 [13,22] 6.271 [15,26] 6.973 [15,25] 7.160 [12,19] 5.631 [13,23] 6.224 [13,18] 5.428 [10,12] 4.680 [11,14] 4.711 [11,16] 5.007 3-HybClip 2-HybClip BezClip 1064 3-HybClip [10,10] 4.539 [10,13] 4.617 [9,14] 4.570 [8,10] 4.258 [9,11] 4.321 [7,12] 4.258 [8,8] 3.993 [7,11] 4.212 [25,49] 16.926 [18,48] 23.509 ¼ [16,40] 14.695 fðtÞ [20,42] 14.461 ððs1=3Þ2 ðs2Þ2 , ðs1=3Þ2 ðs3Þðs þ 1ÞÞ, ½Nf ,Ng  t ¼ (8,8) gðsÞ [11,21] 6.084 ððt1=3Þ2 ðt2Þ2 ðt þ 3Þ4 , ðt1=3Þ2 ðt þ 1Þ5 ðt4ÞÞ, [9,18] 4.992 ¼ [10,20] 5.382 fðtÞ [6,10] 4.056 ððs1=3Þ2 ðs2Þðs þ6Þ, ðs1=3Þ2 ðs3Þðs þ 6ÞÞ, ½Nf ,Ng  t ( ¼ (8,4) ( gðsÞ [6,8] 3.806 Example 3 (Degenerate intersections). We applied algorithms 2HybClip, 3-HybClip, and BezClip to the three pairs of Bézier curves ( fðtÞ ¼ ððt1=3Þ2 ðt3Þðt þ 6Þ, ðt1=3Þ2 ðt þ3Þðt6ÞÞ, [6,9] 3.884 We show experimental results on computing the single degenerate intersections between two curves as follows. ½Nf ,Ng  t Table 4 reports the number pairs of iterations ½Nf ,Ng  and the computing times in seconds for various values of desired accuracy e for computing the tangent intersections between the three pairs of Bézier curves with various degrees (n,m). Fig. 6 visualizes the relation between computing times and desired accuracy. We can see that both 2-HybClip and 3-HybClip generally perform slightly better than BezClip for computing the tangent intersections between curves. Unfortunately, we are not able to give the exact convergence rate in theory for these cases. (4,4) ððs1=3Þ2 ðs2Þ4 ðs þ 1Þ2 , ðs1=3Þðs3=2Þ5 ðs þ 1Þ2 Þ: 2-HybClip ¼ BezClip gðsÞ 3-HybClip ððt1=3Þ2 ðt þ1Þ3 ðt2Þ3 , ðt1=3Þðt2Þ3 ðt þ 1=2Þ4 Þ, 2-HybClip ¼ BezClip fðtÞ 3-HybClip ððs1=3Þ2 ðs2Þðs3Þ, ðs1=3Þðs þ 1=2Þðs þ1Þ2 Þ, 2-HybClip ¼ BezClip gðsÞ 3-HybClip ððt1=3Þ2 ðt þ1Þ3 ðt2Þ3 , ðt1=3Þðt2Þ3 ðt þ 1=2Þ4 Þ, 2-HybClip ¼ 1032 fðtÞ 1016 ððs1=3Þ2 ðs2Þðs3Þ, ðs1=3Þðs þ 1=2Þðs þ1Þ2 Þ, 108 ( ¼ 104 ( gðsÞ e Example 2 (Tangent intersections). We applied algorithm 2-HybClip, 3-HybClip, and BezClip to the three pairs of Bézier curves ( fðtÞ ¼ ððt1=3Þ2 ðt þ1Þðt2Þ, ðt1=3Þðt1Þðt þ 2Þ2 Þ, Degrees (n,m) From Table 3 and Fig. 5, we can see the following observations. Algorithm 2-HybClip performs slightly better than BezClip in running times for these three pairs of Bézier curves. The difference between the overall computing times to achieve a certain accuracy is not that significant although 2-HybClip has fewer times in all examples. However, Algorithm 3-HybClip performs not as well as what we have expected. It seems that its performance depends much on the curve pairs. For the third curve pair, 3-HybClip performs close to 2-HybClip. Both are better than BezClip. For the first curve pair, 3-HybClip performs only a bit better than BezClip. However, for the second curve pair, 3-HybClip performs even worse than BezClip. This is because 3-HybClip involves more computation in solving the cubic polynomial equations and thus needs more time to finish one iteration step. We now show experimental results on computing the single tangent intersections between two curves. BezClip Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 Table 6 Example 4 (multiple intersections): number pairs of iterations ½Nf ,Ng  and computing times t in seconds for various values of accuracy e. (n,m) are degrees of the two curves f,g, respectively. 318 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 0.8 5.4 0.7 5.2 319 t 5 0.6 BezClip 4.8 f 0.5 g 2−HybClip 4.6 3−HybClip 4.4 0.4 4.2 0.3 4 0.2 −1 0 −0.5 0.5 1 2 1.5 0.6 3 4 log2log(1/ε) 5 6 t 0.4 10 0.2 9 0 f 2−HybClip 8 g −0.2 BezClip 7 −0.4 3−HybClip 6 −0.6 −0.8 5 0.8 1 1.2 1.4 1.6 1.8 2 2 1.2 1 3 4 5 log2log(1/ε) 6 t 0.8 35 0.6 0.4 BezClip 30 0.2 g 0 25 2−HybClip f −0.2 20 −0.4 3−HybClip −0.6 15 −0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 2 3 4 5 log2log(1/ε) 6 Fig. 8. Example 4 (multiple intersections). Left: the figures of the curve pairs; right: computing time t in seconds vs. accuracy. The degrees (n,m) of the two curves are (4,4) (upper row), (8,4) (middle row), (8,8) (lower row), respectively. 4.2. Multiple intersections We show experimental results on computing multiple intersections between two curves in this section. Example 4 (Multiple intersections). We applied algorithms 2HybClip, 3-HybClip, and BezClip to the three pairs of Bézier curves. Note that these three pairs have respectively 2, 4, and 8 intersections. ( fðtÞ ¼ 4 3 2 3 2 3 ð51 2 t þ50t 27t þ 2t þ 2 , 5 t þ 10Þ, gðsÞ ¼ 3 39 2 16 1 ðs4 4s3 32 s2 þ4s12 , 26 5 s  5 s þ 5 s þ 5Þ, ¼ 7 84 6 4 336 5 ð25 t 8 12 5 t  5 t þ 5 t 84t 8 fðtÞ > > > > > > > > >>< > > > > > > gðsÞ > > > > : ¼ 2 16 7 þ 56t 3 112 5 t þ 5 t þ 5, 6 5 805 4 1123 8 2074 7 10 t  5 t þ 441t þ 70t  2 t þ 238t 3 42t 2 2t þ 12Þ, 3 3 2 12 13 ð32 s4 16 5 s 5 s þ 5 s þ 10, 1 4 24 3 36 2 14 1 5 s þ 5 s  5 s þ 5 s5Þ, 8 > fðtÞ > > > > > > > > > > >>< > > > > gðsÞ > > > > > > > > > : ¼ 8 7 672 6 4 224 5 ð53 10 t þ 64t  5 t þ 5 t þ 98t 3 112 2 448 5 t þ 5 t þ 1, 7 6 5 4 37 8 4 t þ52t 350t þ588t 350t 2 ¼ þ70t 20t þ1Þ, 1 8 7 84 6 56 5 4 s þ 24 ð10 5 s  5 s þ 5 s þ 14s 3 14 2 8 84 5 s þ 5 s þ 5sþ 1, 4s8 þ2s7 28s5 þ 56s3 42s2 þ 8sÞ: Table 6 reports the number pairs of iterations ½Nf ,Ng  and the computing times in seconds for various values of desired accuracy e for computing the tangent intersections between the three pairs of Bézier curves with various degrees (n,m). Fig. 8 visualizes the relation between computing times and desired accuracy. We can see that both 2-HybClip and 3-HybClip perform better than BezClip for computing the multiple intersections between curves. Note that 2-HybClip and 3-HybClip perform much similar in the case of third curve pair. 5. Conclusion We have proposed the hybrid clipping technique for computing all the intersections between two planar Bézier curves within a certain 320 Q. Lou, L. Liu / Computers & Graphics 36 (2012) 309–320 accuracy in a given domain. The algorithm is based on the convex hull property of Bézier curves. By clipping a fat curve of one curve with a fat line that bounds the other curve, we generate a reduced subdomain that encloses the intersection. Therefore, a sequence of subdomains that is guaranteed to converge to the corresponding intersection will be obtained by combining with bisection steps. We have proved that the hybrid clipping technique has at least a quadratic convergence rate which is at least as fast as Bézier clipping for transversal intersections. Experimental results have shown that the hybrid clipping performs better than Bézier clipping for transversal intersections, much better than Bézier clipping for degenerate intersections, but a slightly better than Bézier clipping for tangent intersections. It is worthwhile pointing out that both tangent intersections and degenerate intersections are rare in practical applications. Therefore, the hybrid clipping technique is practically useful for computing the transversal intersections between planar curves. We guess that the hybrid clipping has higher convergence rate than Bézier clipping at tangent and degenerate intersections. As one of our future works we will try to find it out. Another future work will focus on the extension of the technique to the intersection computation between two rational curves or between two Bézier surfaces. Finally, we can use other methods, for instance, the SLEVEs [16–18] method, to linearly bound the curves and then compute their intersections. It is worthwhile to try this method for curve intersections which is expected to gain better performance. However, the computation of the SLEVEs for the spline curve is a bit complicated and thus makes the convergence hard to analyze. bij ¼ 8  < ð1Þi þ j n i if i Zj; :0 otherwise, i j 8    mX þjþ1 > l m þj þ1 þ l mþ j þ 1 >< ð1Þl þ i i l m þj þ1l cij ¼ l¼i > > :0 if ðnÞ, otherwise, where ðnÞ means 0 rj r nm1, 0 r ir m þ j þ1. Appendix B. Degree elevation of Bézier curve To make this paper self-contained, we also give the formulae for computing the degree elevation of Bézier curve. Suppose P pðtÞ ¼ ki ¼ 0 c~ i Bki,½a, b A Pk½a, b is a degree k(k o n) Bézier curve. As k P½a, b D Pn½a, b , pðtÞ can be elevated to a degree n Bézier curve with P the form pðtÞ ¼ ni¼ 0 ci Bni,½a, b where the control points can be calculated as [2] ðc0 ,c1 , . . . ,cn ÞT ¼ Fnðn þ 1Þðn þ 1Þ Enðn þ 1Þðk þ 1Þ Bkðk þ 1Þðk þ 1Þ ðc~ 0 , c~ 1 , . . . , c~ k ÞT , ðB:1Þ where F and B are the same in Appendix A and ( 1 if i ¼ j; n Eðn þ 1Þðk þ 1Þ ¼ ðeij Þðn þ 1Þðk þ 1Þ , eij ¼ 0 otherwise: Acknowledgement This work is supported by the National Natural Science Foundation of China (61070071) and the National Basic Research Program of China 2011CB302400. Appendix A. Optimal degree reduction of Bézier curve Degree reduction of Bézier curves has been well studied in the literature. To make this paper self-contained, we give the main formulae for computing the optimal L2 approximation (with lower degree) to a given Bézier curve. More details can be found in [19]. P Given a degree n Bézier curve fðtÞ ¼ ni¼ 0 ai Bni,½a, b ðtÞ A Pn½a, b , the control points of its optimal degree k (ko n) Bézier curve P pðtÞ ¼ ki ¼ 0 c~ i Bki,½a, b A Pk½a, b can be computed as ðc~ 0 , c~ 1 , . . . , c~ k ÞT ¼ ðFkðk þ 1Þðk þ 1Þ Bnðk þ 1Þðn þ 1Þ Fkðk þ 1Þðk þ 1Þ Cnðk þ 1ÞðnkÞ ðCnðnkÞðnkÞ Þ1 BnðnkÞðn þ 1Þ Þ  ða0 ,a1 , . . . ,an ÞT , where Bnðn þ 1Þðn þ 1Þ ¼ Cnðn þ 1Þðnk1Þ ¼ Bnðk þ 1Þðn þ 1Þ ! , BnðnkÞðn þ 1Þ Cnðk þ 1ÞðnkÞ ! CnðnkÞðnkÞ Fnðn þ 1Þðn þ 1Þ ¼ ðf ij Þðn þ 1Þðn þ 1Þ , Bnðn þ 1Þðn þ 1Þ ¼ ðbij Þðn þ 1Þðn þ 1Þ , Cnðn þ 1ÞðnkÞ ¼ ðcij Þðn þ 1ÞðnkÞ , with 8    < nj = n i ij f ij ¼ :0 if i Zj; otherwise, , ðA:1Þ References [1] Dokken T. Aspects of intersection algorithms and approximations. PhD thesis. University of Oslo; 1997. [2] Farin G. Curves and surfaces for CAGD: a practical guide. 5th ed. Morgan Kaufmann Publishers Inc.; 2002. [3] Mørken K, Reimers M, Schulz C. Computing intersections of planar spline curves using knot insertion. Comput Aided Geometric Des 2009;26(3): 351–66. [4] Lane J, Riesenfeld R. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans Pattern Anal Mach Intell 1980;2:35–46. [5] Koparkar P, Mudur S. A new class of algorithms for the processing of parametric curves. Comput Aided Des 1983;15:41–5. [6] Sederberg T, Parry S. Comparison of three curve intersection algorithms. Comput Aided Des 1986;18:58–63. [7] Sederberg T, Nishita T. Curve intersection using Bézier clipping. Comput Aided Des 1990;22(9):538–49. [8] Schulz C. Bézier clipping is quadratically convergent. Comput Aided Geometric Des 2009;26(1):61–74. [9] Bartoň M, Jüttler B. Computing roots of polynomials by quadratic clipping. Comput Aided Geometric Des 2007;24(3):125–41. [10] Liu L, Zhang L, Lin B, Wang G. Fast approach for computing roots of polynomials using cubic clipping. Comput Aided Geometric Des 2009;26(5): 547–559. [11] McNamee J. Bibliographies on roots of polynomials. J Comput Appl Math 2002;142:433–4. [12] Bartoň M. B. Jüttler, Computing roots of systems of polynomials by linear clipping. SFB F013 technical report. [13] Moore B, Jüttler B. Computing roots of polynomials using bivariate quadratic clipping. In: The 2nd international conference on mathematical aspects of computer and information sciences; 2007. [14] Mourrain B, Pavone JP. Subdivision methods for solving polynomial equations. J Symbolic Comput 2009;44(3):292–306. [15] Sherbrooke E, Patrikalakis N. Computation of the solutions of nonlinear polynomial systems. Comput Aided Geometric Des 1993;10(5):379–405. [16] Lutterkort D, Peters J. Optimized refinable enclosures of multivariate polynomial pieces. Comput Aided Geometric Des 2001;18(9):851–63. [17] Lutterkort D, Peters J. Tight linear bounds on the distance between a spline and its b-spline control polygon. Numer Math 2001;89:735–48. [18] Peters J, Wu X. SLEVEs for planar spline curves. Comput Aided Geometric Des 2004;21(6):615–35. [19] Zhang R, Wang G. Constrained Bézier curves best multi-degree reduction in the l2-norm. Prog Nat Sci 2005;15(9):843–50.