research-article

Public Access

k-curves: interpolation at local maximum curvature

Authors:

Stephen Schiller,

Gregg Wilensky,

Scott SchaeferAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 36, Issue 4

Article No.: 129, Pages 1 - 7

https://doi.org/10.1145/3072959.3073692

Published: 20 July 2017 Publication History

Abstract

We present a method for constructing almost-everywhere curvature-continuous, piecewise-quadratic curves that interpolate a list of control points and have local maxima of curvature only at the control points. Our premise is that salient features of the curve should occur only at control points to avoid the creation of features unintended by the artist. While many artists prefer to use interpolated control points, the creation of artifacts, such as loops and cusps, away from control points has limited the use of these types of curves. By enforcing the maximum curvature property, loops and cusps cannot be created unless the artist intends for them to be.

To create such curves, we focus on piecewise quadratic curves, which can have only one maximum curvature point. We provide a simple, iterative optimization that creates quadratic curves, one per interior control point, that meet with G² continuity everywhere except at inflection points of the curve where the curves are G¹. Despite the nonlinear nature of curvature, our curves only obtain local maxima of the absolute value of curvature only at interpolated control points.

Supplementary Material

ZIP File (a129-yan.zip)

Supplemental files.

Download
13.66 MB

MP4 File (papers-0476.mp4)

Download
425.24 MB

References

[1]

Phillip J. Barry and Ronald N. Goldman. 1988. A Recursive Evaluation Algorithm for a Class of Catmull-Rom Splines. In Proceedings of SIGGRAPH. 199--204.

[2]

E. Catmull and R. Rom. 1974. A class of local interpolating splines. Computer aided geometric design (1974), 317--326.

[3]

Gilles Deslauriers and Serge Dubuc. 1989. Symmetric iterative interpolation processes. Constructive Approximation 5, 1 (1989), 49--68.

[4]

Nira Dyn, David Levin, and John A. Gregory. 1987. A 4-point Interpolatory Subdivision Scheme for Curve Design. Computer Aided Geometric Design 4, 4 (1987), 257--268.

Digital Library

[5]

Gerald Farin. 2002. Curves and Surfaces for CAGD: A Practical Guide (5th ed.). Morgan Kaufmann Publishers Inc.

[6]

Gerald Farin. 2006. Class A Bézier curves. Computer Aided Geometric Design 23, 7 (2006), 573--581.

Digital Library

[7]

Yu Yu Feng and Jernej Kozak. 1996. On G² continuous interpolatory composite quadratic Bezier curves. J. Comput. Appl. Math. 72, 1 (1996), 141--159.

Digital Library

[8]

He-Jin Gu, Jun-Hai Yong, Jean-Claude Paul, and Fuhua Frank Cheng. 2009. Constructing G¹ quadratic Bézier curves with arbitrary endpoint tangent vectors. International Journal of CAD/CAM 9, 1 (2009).

[9]

Sven Havemann, Johannes Edelsbrunner, Philipp Wagner, and Dieter Fellner. 2013.

[10]

Curvature-controlled curve editing using piecewise clothoid curves. Computers & Graphics 37, 6 (2013), 764--773.

Digital Library

[11]

Masatake Higashi, Kohji Kaneko, and Mamoru Hosaka. 1988. Generation of high-quality curve and surface with smoothly varying curvature. In EG Technical Papers. Eurographics Association.

[12]

Josef Hoschek and Dieter Lasser. 1993. Fundamentals of Computer Aided Geometric Design. A. K. Peters, Ltd.

[13]

Jeffrey M. Lane and R. F. Riesenfeld. 1981. Bounds on a polynomial. BIT Numerical Mathematics 21, 1 (1981), 112--117.

[14]

Raph Levien and Carlo H Séquin. 2009. Interpolating Splines: Which is the fairest of them all? Computer-Aided Design and Applications 6, 1 (2009), 91--102.

[15]

Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local/Global Approach to Mesh Parameterization. In Proceedings of the Symposium on Geometry Processing. 1495--1504.

[16]

James McCrae and Karan Singh. 2009. Sketching piecewise clothoid curves. Computers & Graphics 33, 4 (2009), 452--461.

Digital Library

[17]

Yves Mineur, Tony Lichah, Jean Marie Castelain, and Henri Giaume. 1998. A shape controled fitting method for Bézier curves. Computer Aided Geometric Design 15, 9 (1998), 879--891.

Digital Library

[18]

Kenjiro T Miura and RU Gobithaasan. 2014. Aesthetic curves and surfaces in computer aided geometric design. International Journal of Automation Technology 8, 3 (2014), 304--316.

[19]

Kenjiro T. Miura, Dai Shibuya, R. U. Gobithaasan, and Shin Usuki. 2013. Designing Log-aesthetic Splines with G² Continuity. Computer-Aided Design and Applications 10, 6 (2013), 1021--1032.

[20]

Robert Schaback. 1989. Interpolation with piecewise quadratic visually C² Bézier polynomials. Computer Aided Geometric Design 6, 3 (1989), 219--233.

Digital Library

[21]

Robert Schneider and Leif Kobbelt. 2000. Discrete fairing of curves and surfaces based on linear curvature distribution. Technical Report. DTIC Document.

[22]

Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the Symposium on Geometry Processing. 109--116.

[23]

Norimasa Yoshida, Ryo Fukuda, and Takafumi Saito. 2009. Log-aesthetic Space Curve Segments. In SIAM/ACM Conference on Geometric and Physical Modeling. 35--46.

Digital Library

[24]

Norimasa Yoshida and Takafumi Saito. 2017. Quadratic log-aesthetic curves. Computer-Aided Design and Applications 14, 2 (2017), 219--226.

[25]

Cem Yuksel, Scott Schaefer, and John Keyser. 2011. Parameterization and applications of Catmull-Rom curves. Computer-Aided Design 43, 7 (2011), 747--755.

Digital Library

Cited By

Li K(2024)A class of C^1 rational blending interpolation spline curveProceedings of the 2024 International Conference on Computer and Multimedia Technology10.1145/3675249.3675328(457-461)Online publication date: 24-May-2024
https://dl.acm.org/doi/10.1145/3675249.3675328
Liu XNie HLi DHe YJr M(2024)High-Fidelity and Curvature-Continuous Path Smoothing With Quadratic Bézier CurveIEEE Transactions on Intelligent Vehicles10.1109/TIV.2023.33484849:2(3796-3810)Online publication date: Feb-2024
https://doi.org/10.1109/TIV.2023.3348484
Wang ZCao JGuan TChen ZZhang Y(2024)pκ-Curves: Interpolatory curves with curvature approximating a parabolaComputer Aided Geometric Design10.1016/j.cagd.2024.102330(102330)Online publication date: May-2024
https://doi.org/10.1016/j.cagd.2024.102330
Show More Cited By

Index Terms

k-curves: interpolation at local maximum curvature
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models

Recommendations

Approximation of conic sections by curvature continuous quartic Bézier curves

In this paper we propose two approximation methods of conic section by quartic Bezier curves. These are the extensions of the quartic Bezier approximations of circular arcs presented in Ahn and Kim (1997) [1] and Kim and Ahn (2007) [10] to conic cases. ...
Cubic algebraic curves based on geometric constraints

Methods for curve modeling with cubic algebraic curves based on geometric constraints are introduced in this paper. A 1-parameter family of cubic curves with four given points as well as two tangent lines at the endpoints is constructed in the first ...
$ϵ κ$ -Curves: controlled local curvature extrema
Abstract
The $κ$ -curve is a recently published interpolating spline which consists of quadratic Bézier segments passing through input points at the loci of local curvature extrema. We extend this representation to control the magnitudes of local maximum ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 36, Issue 4

August 2017

2155 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3072959

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must 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 a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2017

Published in TOG Volume 36, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
1,307
Total Downloads

Downloads (Last 12 months)210
Downloads (Last 6 weeks)26

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li K(2024)A class of C^1 rational blending interpolation spline curveProceedings of the 2024 International Conference on Computer and Multimedia Technology10.1145/3675249.3675328(457-461)Online publication date: 24-May-2024
https://dl.acm.org/doi/10.1145/3675249.3675328
Liu XNie HLi DHe YJr M(2024)High-Fidelity and Curvature-Continuous Path Smoothing With Quadratic Bézier CurveIEEE Transactions on Intelligent Vehicles10.1109/TIV.2023.33484849:2(3796-3810)Online publication date: Feb-2024
https://doi.org/10.1109/TIV.2023.3348484
Wang ZCao JGuan TChen ZZhang Y(2024)pκ-Curves: Interpolatory curves with curvature approximating a parabolaComputer Aided Geometric Design10.1016/j.cagd.2024.102330(102330)Online publication date: May-2024
https://doi.org/10.1016/j.cagd.2024.102330
Pijls HQuan L(2023)A Computational Method with Maple for Finding the Maximum Curvature of a Bézier-Spline CurveMathematical and Computational Applications10.3390/mca2802005628:2(56)Online publication date: 8-Apr-2023
https://doi.org/10.3390/mca28020056
Djuren TKohlbrenner MAlexa M(2023)K-Surfaces: Bézier-Splines Interpolating at Gaussian Curvature ExtremaACM Transactions on Graphics10.1145/361838342:6(1-13)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618383
Wang AHe CZheng JZhao G(2023)3D Class A Bézier curves with monotone curvatureComputer-Aided Design10.1016/j.cad.2023.103501159:COnline publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1016/j.cad.2023.103501
NOH SHARADA HYANG XFUKUSATO TIGARASHI T(2022)PPW Curves: a C² Interpolating Spline with Hyperbolic Blending of Rational Bézier CurvesIEICE Transactions on Information and Systems10.1587/transinf.2022PCP0006E105.D:10(1704-1711)Online publication date: 1-Oct-2022
https://doi.org/10.1587/transinf.2022PCP0006
Yuksel C(2022)High-Performance Polynomial Root Finding for GraphicsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35438655:3(1-15)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3543865
Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Binninger ASorkine‐Hornung O(2022)Smooth Interpolating Curves with Local Control and Monotone Alternating CurvatureComputer Graphics Forum10.1111/cgf.1460041:5(25-38)Online publication date: 6-Oct-2022
https://doi.org/10.1111/cgf.14600
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents