Internally, Easel represents many types of 2D shapes using Bézier paths and performs many operations on these curves as you work on your project. One frequent operation is calculating the bounding box of a path – and we recently sped up this calculation tenfold.
Easel used to do this by taking the path…
…then sampling a bunch of points on it…
…and then looking at all of those points to find the min and max X and Y values:
We were unhappy with this for two reasons:
- The result was an approximation limited by the number of samples.
- For complex paths, it required calculating many thousands of sampled points – so it was slow.
To build a faster solution, we went back to the underlying Bézier path representation, which is a series of cubic Bézier curves, each defined by two endpoints () with two control points () in between:
Between each pair of endpoints, the X and Y values are defined by parametric equations with polynomial coefficients determined by the endpoints and and control points and :
Some high school calculus lets us know any points where the X () or Y () derivatives are zero – which is where those functions have their minimum and maximum values:
Those points, and the original endpoints, are the only points we need to consider to find the bounding box for the path:
And not only is it the precise bounding box, but we found it while evaluating far fewer points!