I shared two weeks ago how I built the scissors feature in Loose Leaf; short story, lots and lots of UIBezierPath. As I worked through the algorithm for slicing paths together, it didn’t take me long to realize that default performance of UIBezierPath was… lacking. The only way to introspect the path itself is to create a custom function – not block mind you, function – and use CGPathApply() to iterate the path and calculate what you’re looking for. Every time.
For a path of size N, finding the first point? O(N). Finding points or tangents along the path? O(N). Is the path closed? O(N).
PerformanceBezier improves many of these simple tasks with operations that average to O(1) for any length bezier. The first calculation may still iterate the path, but afterwards the answer will be cached for far faster access, and for some operations a full path iteration is never needed. It also brings UIBezierPath a bit closer to its NSBezierPath counterpart.
And the best part? It works with all UIBezierPath objects – no custom subclass, no extra code, it “just works.”
How ’bout an example?
Scissors isn’t the only feature in Loose Leaf that requires finding intersections and clipping Bezier paths – drawing over images is essentially the same algorithm. With each stroke, I need to clip the pen’s path to each scrap. Even drawing over multiple images will clip the pen’s ink across each image.
With every stroke, the scissor algorithm needs to be run for each image that the pen draws over. To do this in 60FPS means it needs to be done quick. Each image’s border path only changes when it’s cut with scissors, so it makes sense to cache as much information about that path as possible to reduce the cost of future clips with the pen.
So How Much Does It Help?
I’ve included a macro in PerformanceBezier so you can compare times as well. Turning this flag on will simulate running CGPathApply to retrieve the same information. So [path firstPoint] becomes O(N) instead of O(1), etc.
When I run PerformenceBezier without caching on a first gen iPad mini, the FPS drops dramatically. I used instruments to measure how much time was spent in the Main Thread in total, and how much of that time was wasted with uncached Bezier operations.
The Test: I dropped 4 irregularly cut images onto a page, and scribble over them with the pen. This stresses the bezier clipping algorithm as each new stroke segment is clipped to multiple paths.
The results were dramatic. Out of 10s spent on the Main Thread during drawing, 5s were spent wasting time in methods that could’ve been cached. Put another way, this doubled performance in Loose Leaf. After optimizations, I can get twice the clipping done in the same amount of time. Some method calls saw 10x speed improvement. Obviously, your milage will vary depending on your algorithm and how heavily you use UIBezierPath in your code, but Loose Leaf would simply not be possible without these optimizations.
Get the Code
I’m working to open source all of path clipping code for the scissors, and the first step starts today. Stay tuned!