I’ve been working with curvature of parametric curves and quadratic Beziers in particular as part of the project on arc-length parameterization of a general path. A few recent emails have broached this topic. Differential geometry often discusses both extrinsic and intrinsic curvature. Intrinsic curvature is too theoretical for this casual post. Extrinsic curvature is defined on curves embedded into a Euclidean (or other) space. A relationship exists between extrinsic curvature and the radius of the osculating circle (read all about it on Wikipedia).
Extrinsic curvature for parametric curves is well covered in Grey [1]. Given a Bezier curve, B(t), curvature is defined as κ(t) = |B'(t) x B”(t)|/||B'(t)||3 . Now, a quadratic Bezier is a parabola and geometric properties, including curvature, can be computed from parabolic representation or the polynomial coefficients. There are, however, instances where control-point coordinates are immediately available and it is not desirable to compute coefficients. Fortunately, the open literature contains everything we need to work with curvature based solely on the geometric constraints of the quadratic Bezier curve.
Suppose the control points are p0, p1, and p2. Let A represent the area enclosed by the convex hull (triangle in this case) of the control points. Computing the area given the control point coordinates is trivial. Let m be the midpoint of the pop2 segment. The distance, d = ||p0m|| = ||mp2|| is the diameter of two circles passing through p0, m, and p2. A screen shot from the output of a simple Flex program to illustrate these properties is shown below.
p1 is the top, middle control point. m is the red dot.
Sapidis and Frey [2] established that B(t) has monotone curvature if p1 lies inside either circle. Deddi, Everett, and Lazard [3] proved that the maximum curvature of B(t) is ||p1m||3/A2 if p1 lies strictly outside the circles. If inside, the maximum curvature is max(κ0, κ1) where
κ0 = A/||p0p1||3
κ1 = A/||p1p2||3
are the curvature at B(0) and B(1), respectively.
Knowing regions of monotone curvature and relationships between curvature at the endpoints vs. maximum curvature is helpful in that there are nice heuristic relationships between arc length and curvature in these regions. That is, we can subdivide a quadratic Bezier into equivalent quadratics with monotone curvature and use the information to sample the curve to reparameterize on arc length. Only control points immediately available from subdivision are needed.
The appealing feature of this approach is that the geometric constraints of the curve itself determine the sampling, not a predetermined heuristic. This tends to increase both accuracy and efficiency by not undersampling curves with large lengths and points of high curvature or oversampling curves with small length or near linearity.
More to come as this project progresses 🙂
References
[1] Gray, A. Modern Differential Geometry of Curves and Surfaces with Mathematica, 2nd ed. Boca Raton, FL: CRC Press, 1997.
[2] Sapidis, N.S. and Frey, W.H., “Controlling the curvature of a quadratic Bezier curve,” Computer Aided Geometric Design 9, 1992, pp. 85-91
[3] Deddi, H, Everett, H. and Lazard, S., “Interpolation problem with curvature constraint,” In C. Rabut A. Cohen and L. L. Schumaker, editors, Curve and Surface Fitting. Vanderbilt University press, Nashville, 2000.
The Algorithmist 