-Curves: Interpolation At Local Maximum Curvature
κ-Curves: Interpolation at Local Maximum CurvatureZHIPEI YAN, Texas A&M UniversitySTEPHEN SCHILLER, Adobe ResearchGREGG WILENSKY, AdobeNATHAN CARR, Adobe ResearchSCOTT SCHAEFER, Texas A&M UniversityFig. 1. Top row shows example shapes made from the control points below. In all cases, local maxima of curvature only appear at the control points, and thecurves are G 2 almost everywhere.We present a method for constructing almost-everywhere curvature-continuous,piecewise-quadratic curves that interpolate a list of control points and havelocal maxima of curvature only at the control points. Our premise is thatsalient features of the curve should occur only at control points to avoid thecreation of features unintended by the artist. While many artists prefer touse interpolated control points, the creation of artifacts, such as loops andcusps, away from control points has limited the use of these types of curves.By enforcing the maximum curvature property, loops and cusps cannot becreated unless the artist intends for them to be.To create such curves, we focus on piecewise quadratic curves, whichcan have only one maximum curvature point. We provide a simple, iterativeoptimization that creates quadratic curves, one per interior control point,that meet with G 2 continuity everywhere except at inflection points of thecurve where the curves are G 1 . Despite the nonlinear nature of curvature,our curves only obtain local maxima of the absolute value of curvature onlyat interpolated control points.CCS Concepts: Computing methodologies Parametric curve andsurface models;Additional Key Words and Phrases: interpolatory curves, monotonic curvature, curvature continuityThis work was supported by NSF Career award IIS 1148976.Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACMmust be honored. Abstracting with credit is permitted. To copy otherwise, or republish,to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org. 2017 ACM. 0730-0301/2017/7-ART129 15.00DOI: http://dx.doi.org/10.1145/3072959.3073692ACM Reference format:Zhipei Yan, Stephen Schiller, Gregg Wilensky, Nathan Carr, and Scott Schaefer. 2017. κ-Curves: Interpolation at Local Maximum Curvature. ACM Trans.Graph. 36, 4, Article 129 (July 2017), 7 pages.DOI: TIONCurve modeling has a long history in computer graphics, findinguse in drawing, sketching, data fitting, interpolation, as well as animation. This rich application space has led to decades of researchfor both representing and modifying curves. The goal of such curverepresentations is to provide the user with control over the shapeof the curve while building a curve that has certain geometric properties. These properties may include smoothness, interpolation ofvarious points, and locality.In this paper we focus on interpolatory curves; that is, curvesthat interpolate their control points. While much research hasconcentrated on approximating curves, many users prefer directcontrol over salient geometric features of the curve such as theposition of the curve. Yet interpolatory curves have a malignedpast as they can often generate geometric features such as cuspsand loops away from control points that the user has a hard timecontrolling (see Figure 2).Our premise is that salient geometric features should appear onlyat control points for interpolatory curves. Position is one suchexample of a feature that is automatically enforced in interpolatorycurve constructions. However, the question is then: what otherfeatures should appear only at control points? Levien et al. [LevienACM Transactions on Graphics, Vol. 36, No. 4, Article 129. Publication date: July 2017.
129:2 Z. Yan et. al.Fig. 2. Comparison of our result with other C 2 curves. From left to right: 6-point interpolatory subdivision curve [Deslauriers and Dubuc 1989], C 2 Catmull-Romspline [Catmull and Rom 1974], C 2 interpolating cubic B-spline [Farin 2002], our curve.and Séquin 2009] argue that points of maximal curvature are alsosalient features. Indeed, we can see that lack of control of points ofmaximal curvature has led to many of the historical problems withinterpolatory curve constructions. For example, the propensity toproduce cusps is due to a local maximum of curvature (in this case,infinite curvature) being produced away from the control points.We propose to create interpolatory curves where the local maximum of the absolute value of the curvature of the curve only appearsat control points, which we call κ-curves. In addition, we build suchcurves using piecewise quadratic curves that meet with G 2 continuity everywhere except at inflection points, where the join is G 1 . Weshould point out that the primary application envisioned for thesesplines is more for artistic design, as opposed to CAD. Thus theoccasional lack of G 2 continuity is not an issue. Also, because weenvision these curves to be controlled by artists, the curve shouldchange continuously under continuous motion of the control points.This last property is trivially satisfied by many curve constructions,but not all. For example, Figure 3 shows an example of continuousmovement of control points for a clothoid curve [Havemann et al.2013] that produces a discontinuous change of the resulting curve.2More related to our method are classes of curves that, not onlyinterpolate control points, but control curvature in some way. Higashi et al. [Higashi et al. 1988] restricted the locations of controlpoints of Bézier curve to obtain monotonic curvature and create aC 2 spline. “Class A” Bézier curves [Farin 2006; Mineur et al. 1998]have monotonic curvature, but few degrees of freedom and can bedifficult to control. Clothoids, also known as Euler spirals, [Havemann et al. 2013; McCrae and Singh 2009; Schneider and Kobbelt2000] are perhaps the best known such curve. These curves havethe property that the curvature of the curve changes linearly withrespect to arc length. Hence, piecewise clothoid curves have localmaximum curvature magnitude at the interpolated points. Suchcurves would be ideal for our purposes except that continuousmotion of the control points does not always create a continuousdeformation of the curve as is illustrated in Figure 3. Log-aestheticcurves [Miura and Gobithaasan 2014; Miura et al. 2013; Yoshidaet al. 2009; Yoshida and Saito 2017] are similar to clothoids (indeedclothoids are a special case) and have curvature plots that increaseexponentially with respect to arc length. Levein et al. [Levien andSéquin 2009] also describe a two parameter spline family moduloconformal transformations.RELATED WORKThere are large numbers of interpolatory curve constructions thathave been developed, and we cannot provide an exhaustive list butrefer to [Hoschek and Lasser 1993] for many such methods. CatmullRom splines [Barry and Goldman 1988; Catmull and Rom 1974] areone of the more common interpolatory curve representations andare combinations of Lagrange interpolation with B-spline basisfunctions. Subdivision curves [Deslauriers and Dubuc 1989; Dynet al. 1987] can also be used to model interpolatory splines. Cubicsplines, formed from approximating B-splines, interpolate pointswith C 2 continuity through the solution to a tridiagonal systemof equations [Farin 2002]. Different parameterizations, such ascentripetal or chordal, can be used to control the shape of thesecurves as well. In the case of C 1 Catmull-Rom splines, such a choicecan guarantee that no cusps appear except at control points [Yukselet al. 2011]. However, these results do not extend to C 2 Catmull-Romsplines. While all of these constructions build interpolatory curves,even with curvature continuity, none allow control over curvature.Figure 2 shows a comparison of many of these methods versus ourconstruction. Note that all of these curves create cusps or have localmaximum curvature points away from control points except for ourcurve.ACM Transactions on Graphics, Vol. 36, No. 4, Article 129. Publication date: July 2017.Fig. 3. Moving one control point continuously for a piecewise clothoid curvecan result in a discontinuous change in the curve as shown on the rightwhere the curve suddenly flips over.In addition to controlling curvature, our method uses piecewisequadratic curves that meet with G 2 continuity. Most curve constructions require cubic curves to generate C 2 or G 2 curves, but G 2quadratic curves have appeared in the past. Schaback [Schaback1989] created a piecewise quadratic G 2 Bézier curve to interpolatea list of non-inflecting points. This approach creates a quadraticBézier curve between interpolated points but tends to produce flatcurves at the interpolated points. Feng et al. [Feng and Kozak 1996]modified this approach and build a G 2 quadratic curve to interpolatea list of points with associated tangent directions where the endpoints of each quadratic appear between interpolated points. Guet al. [Gu et al. 2009] used quadratic Bézier curves to interpolate alist of points with arbitrary tangent directions with G 1 continuity.
κ-Curves: Interpolation at Local Maximum Curvature 129:3Fig. 4. Cubic curves with different number of local maximum curvaturepoints. From left to right: a cubic curve with one, two, and three localmaximum curvature points highlighted in green.Our approach to creating G 2 quadratic curves differs from all theseapproaches, and we develop an explicit solution of the join pointbetween two quadratics to enforce G 2 continuity. In addition, weconsider the added condition that control points are interpolated atmaximal curvature magnitude locations.3GEOMETRIC CONSTRAINTSWe begin by considering the geometric properties that we require ofthese curves. Specifically, given an ordered set of points p1 . . . pn R2 , we would like to construct a curvature continuous curve (G 2curve) such that the curve interpolates the pi ; that is, there existsparameters ti such that p(ti ) pi . We make the additional assumption that these points form a closed curve and should be treatedcyclically (we relax this assumption in Section 4).Furthermore, we would like any local maximums of the curvaturemagnitude (the absolute value of curvature) to exist only at the pi .This last criterion is based on the assumption that points at whichthe curve bends the most, at least locally, are salient features of thecurve and should be under direct control of the user. Notice thatthis last property does not imply that the derivative of the curvaturemagnitude must be zero at every pi . Hence, curvature may belocally increasing or decreasing at a interpolated point pi . However,if a maximum of the curvature magnitude exists, it appears at aninterpolated point.3.1Interpolation at Local Maximums of CurvatureLike many curve methods, we focus on piecewise polynomial curvesas our curve representation. We represent our curves in Bézier form.Given a set of control points c i, j , the i t h Bézier curve of degree d isgiven bydÕd!c i (t) (1 t)d j t j c i, j(d j)!j!j 0where t [0, 1].However, controlling curvature for polynomial curves is difficultat best. Cubic parametric curves can have three local maxima of thecurvature magnitude in any given segment. Figure 4 shows severalparametric cubic Bézier curves with the local maxima of curvaturemagnitude highlighted. While “class A” Bézier curves exist [Farin2006] and have monotonic curvature, they are extremely restrictiveand have few degrees of freedom.Given that maximal curvature is so difficult to control for polynomial curves, we opt for an extremely simple representation forour curves, which we construct out of piecewise quadratic BézierFig. 5. The notation for our control points c i, 0. . .2 , interpolated input pointspi and the G 2 join conditioncurves; one curve (c i (t)) for each interpolated point pi . Individualquadratic curves have the property that they possess at most onepoint of maximum curvature, which is crucial for our application.Let c i,0 , c i,1 , c i,2 R2 be the three control points for the quadraticcurve c i (t). The curvature of this curve is given by c (t ) 2 c (t )κi (t) i, ti 2 )det( t c i (t ) 3 t (c i,0 , c i,1 , c i,2 ) (1 t)(c i,1 c i,0 ) t(c i,2 c i,1 ) 3(1)where gives the area of the triangle specified by its arguments.Taking the derivative of κi (t) and setting the equation equal to zerogives the parameter ti for the point of maximal curvature in termsof the Bézier coefficients for the i th Bézier curve(c i,0 c i,1 ).(c i,0 2c i,1 c i,2 )ti .(2) c i,0 2c i,1 c i,2 2Now to construct a curve c i (t) such that c i (ti ) pi , we will showthat, for any c i,0 , c i,2 , and pi , there exists a choice of c i,1 such thatpi is interpolated at the point of maximal curvature. Starting withthe conditionc i (ti ) pi ,we solve for the point c i,1 and obtainc i,1 pi (1 ti )2c i,0 ti2c i,2.(3)2ti (1 ti )Substituting Equation 3 into Equation 2 results in a cubic equationin terms of ti . c i,2 c i,0 2ti3 3(c i,2 c i,0 ).(c i,0 pi )ti2 (3c i,0 2pi c i,2 ).(c i,0 pi )ti c i,0 pi 2 0.(4)While this equation could have three real roots, which would meanthe solution is not unique, we show in Appendix A that this equationhas exactly one real root in [0, 1] for any choice of c i,0 , pi , c i,2 . Giventhat there is exactly one root of this cubic, finding the root is simple,and there are many ways to do so. We use the exact formula forroots of a cubic in our implementation. Even in the degenerate casewhere all three points form a straight line (i.e; pi (1 α)c i,0 ACM Transactions on Graphics, Vol. 36, No. 4, Article 129. Publication date: July 2017.
129:4 Z. Yan et. al.αc i,2 ), the cubic trivially has one root of ti α. Once we haveti , substituting this value into Equation 3 completes the quadraticcurve that interpolates pi at the point of local maximum curvaturemagnitude.3.2SmoothnessWhile we have discussed a local construction for interpolating pointswhere the curve has maximum curvature magnitude, we aim topiece these curves together to form a curvature continuous (i.e; G 2curve). Note that it is not possible to create a G 2 everywhere curveusing piecewise quadratics if the sign of curvature changes alongthe curve. The reason is that quadratic curves cannot possess zerocurvature unless the curve is trivially a straight line. Hence, unlessour curves are strictly convex, we cannot hope to build piecewisequadratic curves that are G 2 everywhere.Our compromise is to build piecewise quadratic curves that areG 2 almost everywhere. The only place where our curves will losecontinuity of curvature will be at points where the curve changesfrom convex to concave or vice versa. Hence, unlike standard splineconstructions, the geometric smoothness of our piecewise construction changes dependent on the geometry of the curve instead of howthe curve is decomposed into polynomial pieces. Conditions forjoining quadratic curves with G 2 smoothness have been discussedbefore [Schaback 1989]. However, given that it is not well knownthat building curvature continuous quadratic curves is even possible,we derive the conditions here and provide a closed-form solution,which will then be part of our optimization in Section 4.Our curves consist of one quadratic curve, with control pointsc i,0 , c i,1 , c i,2 , per interpolated point pi . The C 0 continuity conditionsbetween curves are trivial and simply require that c i,2 c i 1,0 . G 1continuity is simple as well and requires thatc i,2 (1 λi )c i,1 λi c i 1,1(5)where λi (0, 1).For G 2 continuity, we consider the convex curve in Figure 5. Sincec i,2 is a linear combination of c i,1 and c i 1,1 , the question is if thereis a choice of λi [0, 1] that leads to curvature continuity. G 2continuity requires κi (1) κi 1 (0). Using Equation 1 and writingthe G 2 condition in terms of the control points and λi yields (c i,0 , c i,1 , c i 1,1 ) c i,1 c i 1,1 3 λi2 (c i,1 , c i 1,1 , c i 1,2 ). c i,1 c i 1,1 3 (1 λi )2(6)This condition creates a quadratic equation in terms of λi that hasexactly one root in (0, 1), which isp (c i,0 , c i,1 , c i 1,1 )λi p.p (c i,0 , c i,1 , c i 1,1 ) (c i,1 , c i 1,1 , c i 1,2 )When the convexity of the curve changes, the curve cannot beG 2 since quadratic curves cannot have zero curvature unless theydegenerate to a line. In this case, we choose λi by minimizing thedifference of the curvature magnitude squaredmin( κi (1) κi 1 (0) )2 .λiSince the curvatures of are opposite signs, such a minimization isequivalent to solving κi (1) κi 1 (0) 0 for λi . Using the expressionsACM Transactions on Graphics, Vol. 36, No. 4, Article 129. Publication date: July 2017.Fig. 6. Iterations of our optimization showing convergence with controlpoints (black boxes) and maximum curvature positions (green dots). Fromleft to right: our initial guess, after 1 iteration, after 2 iterations, and finalconvergence after 30 iterations.for curvature in Equation 6, we again find one root for the quadraticequation in (0, 1) given byq (c i,0 , c i,1 , c i 1,1 ).(7)λi qq (c i,0 , c i,1 , c i 1,1 ) (c i,1 , c i 1,1 , c i 1,2 )Note that this equation is identical to the previous expression for λiexcept for the absolute value. Hence, this expression unifies bothcases. In the purely convex case, this choice of λi yields a G 2 curvewhereas the curve is G 1 when the convexity of the curve changes.However, in this case, the absolute value of curvature (but not thesign of curvature) matches at the join between curves.The above equations for for λi will be undefined if both triangleareas in the denominators are zero, which can happen when enoughof the c i, j are co-linear or coincident. This case can be robustlyhandled by adding a small constant, ϵ 10 10 , to the square rootsof each such area.4OPTIMIZATIONUsing the geometric conditions in Section 3, we combine theseconditions together to generate an optimization to find a curvethat satisfies these properties. To do so, we adopt a local/globalapproach [Liu et al. 2008; Sorkine and Alexa 2007]. Our degrees offreedom in the optimization are the off-the-curve points c i,1 sincec i,2 c i 1,0 by the C 0 condition and c i,2 (1 λi )c i,1 λi c i 1,1by the G 1 and G 2 conditions.Given the current solution for c i,0, .,2 , we perform a local stepand estimate the λi using Equation 7 and then update the c i,0 andc i,2 using Equation 5. Next we compute the maximum parametersti from Equation 4. For the first iteration, we use the initial guessthat λi 12 and c i,1 pi . Using these locally computed values, weassume the ti and λi are constant and solve a global, linear systemfor the c i,1 such that (1) c i (ti ) pi and (2) the constraints fromEquation 5 hold. These constraints lead to linear equations for eachpi in the unknowns c i 1,1 , c i,1 , c i 1,1 of the form:pi (1 λi 1 )(1 ti )2c i 1,1 λi ti2c i 1,1 (λi 1 (1 ti )2 (2 (1 λi )ti )ti )c i,1 .Solving this circulant, tridiagonal system of linear equations leadsto updated positions for the c i,1 . We then repeat this solving processuntil convergence.This optimization converges quickly and each iteration is fastto compute since we only solve a small, sparse linear system ofequations. Figure 6 shows the progress of our optimization. After
κ-Curves: Interpolation at Local Maximum Curvature 129:5Fig. 8. The red control point is not at a critical point of curvature, which isdecreasing. However, all local maxima of curvature magnitude appear atcontrol points.Fig. 7. Our curve (brown) shown with contro
GREGG WILENSKY, Adobe NATHAN CARR, Adobe Research SCOTT SCHAEFER, Texas A&M University Fig. 1. Top row shows example shapes made from the control points below. In all cases, local maxima of curvature only appear at the control points, and the . Additional Key Words and Phrases: interpolatory curves, monotonic curva-ture, curvature continuity
channel impulse response in all OFDM symbols are sent. Two channel estimates obtained from the adjacent pilot symbols used for channel estimation on the data between them. There are various types of such one-dimensional interpolation, linear interpolation, cubic spine -interpolation, low pass interpolation, ond -order interpolation.
Quadratic Interpolation: Polynomial Interpolation Given: (x 0, y 0) , (x 1, y 1) and (x 2, y 2) A parabola passes from these three points. Similar to the linear case, the equation of this parabola can be written as f 2 ( x ) b 0 b 1 ( x x 0) b 2 ( x x 0)( x x 1) Quadratic interpolation formula How to find b 0, b 1 and b
SOLIDWORKS creates surface bodies by forming a mesh of curves called U-V curves. The U curves run along a 4-sided surface and are shown in the magenta color. The curves that run perpendicular to the U curves are called the V Curves, and they are shown in the green color. Certain commands may offer the preview mesh where these
Figure 10. Centrifugal Pump Performance Curves 37 Figure 11. Family of Pump Performance Curves 38 Figure 12. Performance Curves for Different Impeller Sizes 38 Figure 13. Performance Curves for a 4x1.5-6 Pump Used for Water Service 39 Figure 14. Multiple Pump Operation 44 Figure 15. Multiple-Speed Pump Performance Curves 45 Figure 16.
applications. Smooth degree-3 curves, known as elliptic curves, were used in Andrew Wiles’s proof of Fermat’s Last Theorem [11]. The points on elliptic curves form a group with a nice geometric description. Hendrick Lenstra [5] exploited this group structure to show that elliptic curves can be used to factor large numbers with a relatively .
Sebastian Montiel, Antonio Ros, \Curves and surfaces", American Mathematical Society 1998 Alfred Gray, \Modern di erential geometry of curves and surfaces", CRC Press 1993 5. 6 CHAPTER 1. CURVES . Contents: This course is about the analysis of curves and surfaces in 2-and 3-space using the tools of calculus and linear algebra. Emphasis will
Hermite Curves Bezier Curves and Surfaces [Angel 10.1-10.6] Parametric Representations Cubic Polynomial Forms Hermite Curves Bezier Curves and Surfaces . Hermite geometry matrix M H satisfying. 02/11/2003 15-462 Graphics I 25 Blending FunctionsBlending Functions Explicit Hermite geometry matrix
possibility of a leak from a storage tank? MANAGING RISK This starts with the design and build of the storage tank. International codes are available, for example API 650, which give guidance on the matter. The following is an extract from that standard: 1.1.1 This standard covers material, design, fabrication, erection, and testing
