Is there an alternative to CGPath which allows to compute points on a path for a given location?

Question

For an animation timing algorithm I need to supply a path as the curve. Probably a bezier curve with control points on both ends.

The problem is that it seems not possible to calculate points on a CGPath because CGPathRef is opaque. Also Apple provides no mechanism to compute points on a path.

Is there a library or utility class which can compute points on a bezier curve or path, for a given location like 0.5 for the middle along the path?

Or let me rephrase it: If CGPath / CGPathRef makes this impossible because it is opaque, and if you only care about bezier curves, is there a way to compute points for locations along the path?

Millais

Hi, openfrog. What does it mean "opaque" as far as CGPath / CGPathRef goes? You are not talking about opacity, I suppose. I had the same problem trying to fetch points on a CGPath given that I knew the controls points, start and end points. – Convolve

Answer 1

The math behind a Bézier path is actually "just":

start⋅(1-t)³ + 3⋅c₁⋅t(1-t)² + 3⋅c₂⋅t²(1-t) + end⋅t³

This means that if you know, the start, the end and both control points (c₁ and c₂), then you can calculate the value for any t (from 0 to 1).

It the values are points (like in the image below) then you can do these calculations separately for x and y.

This is form my explanation of Bézier paths here and the code to update the orange circle as the slider changes (in Javascript) is simply this (it shouldn't be too hard to translate into Objective-C or simply C but I was too lazy):

var sx = 190; var sy = 80; // start
var ex = 420; var ey = 250; // end

var c1x = -30; var c1y = 350; // control point 1
var c2x = 450; var c2y = -20; // control point 2

var t = (x-minSliderX)/(maxSliderX-minSliderX); // t from 0 to 1

var px = sx*Math.pow(1-t, 3) + 3*c1x*t*Math.pow(1-t, 2) + 3*c2x*Math.pow(t,2)*(1-t) + ex*Math.pow(t, 3);
var py = sy*Math.pow(1-t, 3) + 3*c1y*t*Math.pow(1-t, 2) + 3*c2y*Math.pow(t,2)*(1-t) + ey*Math.pow(t, 3);
// new point is at (px, py)

Tati

This is correct, but it's worth noting that the pow() function is extremely slow compared to hand-multiplying. If you need to calculate a lot of points, it can have a serious impact (I usually discourage premature optimizations, but pow() is so slow for squaring and cubing that it really is worth the tiny trouble required to expand it). I discuss Bézier calculation in ObjC in a couple of articles: robnapier.net/blog/fast-bezier-intro-701 and robnapier.net/blog/faster-bezier-722. – Dyarchy

Just one other side note: moving along a Bézier is not linear. While 0.5 will be in the middle, 0.25 will not be a quarter of the way along it. If you need to move along a curve smoothly, you have to compute curve lengths, with is not trivial. For an example of that kind of function, see offsetAtDistance:fromPoint:offset: in github.com/iosptl/ios6ptl/blob/master/ch26/CurvyText/CurvyText/… – Dyarchy

@RobNapier the links in your first comment are broken. Is it possible to update? – Sumerlin

Now: robnapier.net/fast-bezier-intro and robnapier.net/faster-bezier – Dyarchy

Answer 2

Point location calculation from CGPath (Swift 4).

extension Math {

   // Inspired by ObjC version of this code: https://github.com/ImJCabus/UIBezierPath-Length/blob/master/UIBezierPath%2BLength.m
   public class BezierPath {

      public let cgPath: CGPath
      public let approximationIterations: Int

      private (set) lazy var subpaths = processSubpaths(iterations: approximationIterations)
      public private (set) lazy var length = subpaths.reduce(CGFloat(0)) { $0 + $1.length }

      public init(cgPath: CGPath, approximationIterations: Int = 100) {
         self.cgPath = cgPath
         self.approximationIterations = approximationIterations
      }
   }
}

extension Math.BezierPath {

   public func point(atPercentOfLength: CGFloat) -> CGPoint {

      var percent = atPercentOfLength
      if percent < 0 {
         percent = 0
      } else if percent > 1 {
         percent = 1
      }

      let pointLocationInPath = length * percent
      var currentLength: CGFloat = 0
      var subpathContainingPoint = Subpath(type: .moveToPoint)
      for element in subpaths {
         if currentLength + element.length >= pointLocationInPath {
            subpathContainingPoint = element
            break
         } else {
            currentLength += element.length
         }
      }

      let lengthInSubpath = pointLocationInPath - currentLength
      if subpathContainingPoint.length == 0 {
         return subpathContainingPoint.endPoint
      } else {
         let t = lengthInSubpath / subpathContainingPoint.length
         return point(atPercent: t, of: subpathContainingPoint)
      }
   }

}

extension Math.BezierPath {

   struct Subpath {

      var startPoint: CGPoint = .zero
      var controlPoint1: CGPoint = .zero
      var controlPoint2: CGPoint = .zero
      var endPoint: CGPoint = .zero
      var length: CGFloat = 0

      let type: CGPathElementType

      init(type: CGPathElementType) {
         self.type = type
      }
   }

   private typealias SubpathEnumerator = @convention(block) (CGPathElement) -> Void

   private func enumerateSubpaths(body: @escaping SubpathEnumerator) {
      func applier(info: UnsafeMutableRawPointer?, element: UnsafePointer<CGPathElement>) {
         if let info = info {
            let callback = unsafeBitCast(info, to: SubpathEnumerator.self)
            callback(element.pointee)
         }
      }
      let unsafeBody = unsafeBitCast(body, to: UnsafeMutableRawPointer.self)
      cgPath.apply(info: unsafeBody, function: applier)
   }

   func processSubpaths(iterations: Int) -> [Subpath] {

      var subpathArray: [Subpath] = []
      var currentPoint = CGPoint.zero
      var moveToPointSubpath: Subpath?
      enumerateSubpaths { element in
         let elType = element.type
         let points = element.points
         var subLength: CGFloat = 0
         var endPoint = CGPoint.zero
         var subpath = Subpath(type: elType)
         subpath.startPoint = currentPoint

         switch elType {
         case .moveToPoint:
            endPoint = points[0]
         case .addLineToPoint:
            endPoint = points[0]
            subLength = type(of: self).linearLineLength(from: currentPoint, to: endPoint)
         case .addQuadCurveToPoint:
            endPoint = points[1]
            let controlPoint = points[0]
            subLength = type(of: self).quadCurveLength(from: currentPoint, to: endPoint, controlPoint: controlPoint,
                                                       iterations: iterations)
            subpath.controlPoint1 = controlPoint
         case .addCurveToPoint:
            endPoint = points[2]
            let controlPoint1 = points[0]
            let controlPoint2 = points[1]
            subLength = type(of: self).cubicCurveLength(from: currentPoint, to: endPoint, controlPoint1: controlPoint1,
                                                        controlPoint2: controlPoint2, iterations: iterations)
            subpath.controlPoint1 = controlPoint1
            subpath.controlPoint2 = controlPoint2
         case .closeSubpath:
            break
         }
         subpath.length = subLength
         subpath.endPoint = endPoint
         if elType != .moveToPoint {
            subpathArray.append(subpath)
         } else {
            moveToPointSubpath = subpath
         }
         currentPoint = endPoint
      }

      if subpathArray.isEmpty, let subpath = moveToPointSubpath {
         subpathArray.append(subpath)
      }
      return subpathArray
   }

   private func point(atPercent t: CGFloat, of subpath: Subpath) -> CGPoint {
      var p = CGPoint.zero
      switch subpath.type {
      case .addLineToPoint:
         p = type(of: self).linearBezierPoint(t: t, start: subpath.startPoint, end: subpath.endPoint)
      case .addQuadCurveToPoint:
         p = type(of: self).quadBezierPoint(t: t, start: subpath.startPoint, c1: subpath.controlPoint1, end: subpath.endPoint)
      case .addCurveToPoint:
         p = type(of: self).cubicBezierPoint(t: t, start: subpath.startPoint, c1: subpath.controlPoint1, c2: subpath.controlPoint2,
                              end: subpath.endPoint)
      default:
         break
      }
      return p
   }

}

extension Math.BezierPath {

   @inline(__always)
   public static func linearLineLength(from: CGPoint, to: CGPoint) -> CGFloat {
      return sqrt(pow(to.x - from.x, 2) + pow(to.y - from.y, 2))
   }

   public static func quadCurveLength(from: CGPoint, to: CGPoint, controlPoint: CGPoint, iterations: Int) -> CGFloat {
      var length: CGFloat = 0
      let divisor = 1.0 / CGFloat(iterations)

      for idx in 0 ..< iterations {
         let t = CGFloat(idx) * divisor
         let tt = t + divisor
         let p = quadBezierPoint(t: t, start: from, c1: controlPoint, end: to)
         let pp = quadBezierPoint(t: tt, start: from, c1: controlPoint, end: to)
         length += linearLineLength(from: p, to: pp)
      }
      return length
   }

   public static func cubicCurveLength(from: CGPoint, to: CGPoint, controlPoint1: CGPoint,
                                       controlPoint2: CGPoint, iterations: Int) -> CGFloat {
      let iterations = 100
      var length: CGFloat = 0
      let divisor = 1.0 / CGFloat(iterations)

      for idx in 0 ..< iterations {
         let t = CGFloat(idx) * divisor
         let tt = t + divisor
         let p = cubicBezierPoint(t: t, start: from, c1: controlPoint1, c2: controlPoint2, end: to)
         let pp = cubicBezierPoint(t: tt, start: from, c1: controlPoint1, c2: controlPoint2, end: to)
         length += linearLineLength(from: p, to: pp)
      }
      return length
   }

   @inline(__always)
   public static func linearBezierPoint(t: CGFloat, start: CGPoint, end: CGPoint) -> CGPoint{
      let dx = end.x - start.x
      let dy = end.y - start.y
      let px = start.x + (t * dx)
      let py = start.y + (t * dy)
      return CGPoint(x: px, y: py)
   }

   @inline(__always)
   public static func quadBezierPoint(t: CGFloat, start: CGPoint, c1: CGPoint, end: CGPoint) -> CGPoint {
      let x = QuadBezier(t: t, start: start.x, c1: c1.x, end: end.x)
      let y = QuadBezier(t: t, start: start.y, c1: c1.y, end: end.y)
      return CGPoint(x: x, y: y)
   }

   @inline(__always)
   public static func cubicBezierPoint(t: CGFloat, start: CGPoint, c1: CGPoint, c2: CGPoint, end: CGPoint) -> CGPoint {
      let x = CubicBezier(t: t, start: start.x, c1: c1.x, c2: c2.x, end: end.x)
      let y = CubicBezier(t: t, start: start.y, c1: c1.y, c2: c2.y, end: end.y)
      return CGPoint(x: x, y: y)
   }

   /*
    *  http://ericasadun.com/2013/03/25/calculating-bezier-points/
    */
   @inline(__always)
   public static func CubicBezier(t: CGFloat, start: CGFloat, c1: CGFloat, c2: CGFloat, end: CGFloat) -> CGFloat {
      let t_ = (1.0 - t)
      let tt_ = t_ * t_
      let ttt_ = t_ * t_ * t_
      let tt = t * t
      let ttt = t * t * t

      return start * ttt_
         + 3.0 *  c1 * tt_ * t
         + 3.0 *  c2 * t_ * tt
         + end * ttt
   }

   /*
    *  http://ericasadun.com/2013/03/25/calculating-bezier-points/
    */
   @inline(__always)
   public static func QuadBezier(t: CGFloat, start: CGFloat, c1: CGFloat, end: CGFloat) -> CGFloat {
      let t_ = (1.0 - t)
      let tt_ = t_ * t_
      let tt = t * t

      return start * tt_
         + 2.0 *  c1 * t_ * t
         + end * tt
   }
}

Usage:

let path = CGMutablePath()
path.move(to: CGPoint(x: 10, y: 10))
path.addQuadCurve(to: CGPoint(x: 100, y: 100), control: CGPoint(x: 50, y: 50))
let pathCalc = Math.BezierPath(cgPath: path)
let pointAtTheMiddleOfThePath = pathCalc.point(atPercentOfLength: 0.5)

Chronology

This is exactly what I was looking for, thank s so much. – Trout

Answer 3

If you already have the control points to the bezier curve you would like to use for the timing function (of what I presume to be CAAnimation), then you should use the following function to get the appropriate timing function:

[CAMediaTimingFunction functionWithControlPoints:(float)c1x :(float)c1y :(float)c2x :(float)c2y]

However, if what you are trying to do is calculate the Y-locaiton of a bezier curve for a given X-location, you will have to calculate that yourself. Here is a reference for how to do so: Bezier Curves

Potentilla