Improving UIBezierPath Performance and API

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).

Enter PerformanceBezier.

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

Download and browse the code: https://github.com/adamwulf/PerformanceBezier. This isn’t the first repo I’m open sourcing – there’s lots more code from Loose Leaf, and more to come

I’m working to open source all of path clipping code for the scissors, and the first step starts today. Stay tuned!

Step by Step App Store Optimization: An Objective Measure to Find the Best Keywords

When I launched Loose Leaf, I’d heard about how bad app discovery was in the App Store, so I’d assumed any search optimization I did for the App Store would be a wasted effort. If quality Twitter apps are outranked by unrelated apps, it seems like a crap shoot to even try, so I didn’t.

Big mistake. It turns out that roughly half of users are finding and downloading apps through App Store search. Put another way, by not optimizing for App Store search, I’ve effectively cut my sales in half.

Over the past month, I’ve started diving into ASO – App Store Optimization – and finding the best practices, and most of all, finding exact step-by-steps that I can follow. Knowing that “keywords are important” is only half the battle. How do i decide which keywords to use and why? How can I turn this black art into a spreadsheet, and how can I do it for free?

Step 1: Get the Free Spreadsheet

I’ve setup a free spreadsheet with some example data that you can use. You can easily copy it to your own Google Drive to start editing and swapping in your own targeted keywords.

Step 2: Finding Keywords with Sensor Tower

Screen Shot 2015-01-30 at 4.16.08 PMA great resource for finding relevant keywords for your app is SensorTower.com. This site can track your App Store search rankings for any of your keywords, and it also helps with finding new keywords that you may want to use – it’s the 2nd case we’re worried about here.

Screen Shot 2015-01-30 at 4.17.22 PMCreate a free account, then login and add your app to their system. Next, head to the Track Competitors section – you’ll likely see it pre-populated with probable competitors, or you can also look up specific apps. Once you find a close competitor, click the Keyword Spy button. This will take you to a page that’ll show your vs their keywords.

Add each of these keywords to your spreadsheet, and repeat the process for each competitor.

Step 3: Finding Keyword Value

By now, you should have a long list of potential keywords, with very little idea of which keywords are actually valuable. This is our next step: let’s track down which of these keywords are actually worthwhile.

Screen Shot 2015-01-30 at 4.33.00 PMNext up: the Keyword Research tool in SensorTower. For each keyword you’ve added to your spreadsheet, search for that word in this research tool. It’ll give you the Traffic, iPhone/iPad Difficulty, and number of apps for each keyword. Add each of these values into the spreadsheet.

Note: To make this process quicker, you can start the free trial of Sensor Tower and track those keywords in your account. This’ll let you download a single spreadsheet that you can then import into the Google Spreadsheet – but again, it’s only a 2 week trial.

As you add each of these words into the spreadsheet, you should see the rest of the columns fill in automatically.

Step 4: Choosing the Right Keywords

And now you have all the information you need to choose valuable and meaningful keywords for your App Store Optimization. Let’s dig into the spreadsheet and find out what’s going on.

The Sensor Tower data tells you 3 pieces of very important data: How much search traffic that keyword generates and how difficult (0-10) it is to rank for that keyword. So to determine the value of a keyword, we first find how easy it is to rank for a particular word (10-difficulty), then we average the iPad/iPhone values and multiply by the total search traffic to estimate our Traffic Return if we ranked for that keyword.

Screen Shot 2015-01-30 at 4.49.27 PMApple only gives us 100 characters to work with in the keywords field in iTunesConnect, so not all keywords are equal. If two keywords would pull in the same estimated traffic, it only makes sense to choose the shorter word, right? That’s what that last column does, it divides that estimated traffic by the length of the word so you can more equally compare any two keywords.

Once you’ve entered all your keywords and data, just sort by Traffic/Letter to see the most valuable keywords at the top of the list!

Step 5: Enjoy a Coffee!

Now you have an objective measure of which keywords to use in your App Name and Keyword fields, and most importantly you know why they’re valuable – that’s enough to make any engineer smile! 🙂

The Making of Loose Leaf’s Killer Feature: Scissors

I easily spent the most time during development on the scissors tool, which might be surprising given how simple it is to use. You can see a quick example below. Just like real scissors, you can easily slice your pictures into any shape.

It seems simple enough right, so what makes this so tough? The next example shows just how robust the scissors are. For a dramatically bizarre shape, they still cut it into pieces just as you’d expect, and quickly at that. And it even supports cutting holes into scraps too.  

We’re getting closer to seeing why this is so tough: it’s cutting arbitrary shapes with an arbitrary path into an arbitrary number of sub-shapes or holes, and doing this quickly enough on a relatively small mobile processor.

First: The Model

Before we can dive into how the slice happens, we have to understand how the data is modeled.

Each scrap is at least is a closed (looped) outer Bézier path with potentially many inner paths. Each of those Bézier paths is actually made up of many segments, each of which is a single cubic Bézier curve. Following along these path elements shows up the direction of that path. The enclosed subpaths are always in the reverse direction of the outer shape path.

You can see an arbitrary shape here, along with its numbered segments and path direction. Next to it is a simple 3 segment scissor cut.

numbered-shapenumbered-scissors

With only these two paths, we can determine how to cut the original shape into its smaller pieces.

Second: The Algorithm

In the picture above, it’s obvious to us humans where the new scraps would be, but for a computer to calculate the new shapes, it has to detect where the shape’s path and the scissor’s path intersect. This gives us the key pieces that show which segments of the scissor’s line will be edges of new subshapes, and which pieces we can safely ignore.

Once we find these intersection points, we can throw away all pieces of the scissors that aren’t inside of the shape. Next we compile a list of all segments of the shape, their direction, and the intersecting segments of the scissors, and their direction. The scissors’ segments are special, and we duplicate these, one for each direction.

intersectionspath-with-direction-2

After all of this path processing, we’re finally ready to calculate the paths of our new sliced shape!

Now we follow these simple rules:

  1. each of the shape’s segments can be used only once
  2. pick any of the scissor segments of either direction
  3. follow it along its direction to the next intersection
  4. follow the arrows, turning left at each intersection, until you reach the original segment again
  5. continue until you run out of segments to use

Third: The Output

Tracing along the edges in this way, and you’ll easily compile up a list of the new shapes.

Fourth: Debugging

The real difficulty of this process came from a number of reasons:

  1. The UIBezierPath class for iOS is extremely lacking, especially when compared to NSBeizerPath in OS X
  2. There are no built in methods to find intersection points or splitting of Bezier paths or curves
  3. By default, accessing any element of a UIBezierPath requires looping through the entire path, making most any algorithm performance terrible

All of that means that I needed to write lots of Bezier specific code, which generally means lots of bugs too.

I used unit tests to verify as much of my code as I could, but it was very had to catch every edge case – especially when the scissors and shape would be at tangents. To help find these edge cases, I also write a small iOS app that’d let me draw any shape and then cut it with any scissor path. This let me try new shapes and cuts extremely quickly – I even gave the app to my 5yo daughter and asked her to try and break it.

Anytime the app threw an exception or otherwise had a problem – it would email me the paths of the shape and scissors for me to debug and add to my unit tests. In this way, I slowly built up a library of unit tests as I worked toward a robust solution.

Fifth: References

For anyone looking to write code for Bezier paths, I highly suggest the following reading and resources:

  1. A Primer on Bézier Curves – http://pomax.github.io/bezierinfo/
  2. KevinLinDev Geometry Tutorial – http://www.kevlindev.com/gui/math/polynomial/
  3. DrawKit – http://apptree.net/drawkit.htm
Google Author link
Page 6 of 50« First...45678...203040...Last »