週間前に、 Loose Leaf の はさみツールの機能をどのように開発したか をご紹介しました。かいつまんで言えば、UIBezierPathを多用する方法です。スライスパスを分割するアルゴリズムを作成し始めてすぐに気付いたのですが、デフォルトのUIBezierPathのパフォーマンスは不十分です。スライスパスそのものを判断するのにもカスタムの関数を作らなければならず(関数です。心を閉ざさないで)、CGPathApply()を使って繰り返し処理でパスをたどり、必要な計算を行わなければなりません。毎回です。

長さNのパスの場合、始点を見つけるのにO(N)、パス内の制御点や交差を見つけるのにO(N)、パスが閉じているかを判定するのにO(N)の計算が必要になります。

PerformanceBezier を使いましょう。

PerformanceBezierはあらゆる長さのベジェ曲線について、こうした単純な操作を平均O(1)の計算量で実現することを可能にします。最初の計算こそパスを繰り返し処理でたどりますが、その後は計算結果がキャッシュされ、高速にアクセスできるようになります。その結果いくつかの操作ではパス全体をたどる必要はなくなります。またPerformanceBezierによって、UIBezierPathは同等のツールであるNSBezierPathに一歩近づきます。

PerformanceBezierの最大の長所は何でしょう？　それはUIBezierPathの全てのオブジェクトにそのまま適用できるということです。カスタムのサブクラスも、追加のコードも必要ありません。“それだけで機能する”のです。

サンプルはいかがですか？

Loose Leafの中で、交差を見つけベジェ曲線のパスを切り取る処理を必要とするのは、はさみツールの機能だけではありません。画像の上に絵を描くのも本質的には同じアルゴリズムを使います。線が描かれる度に、ペンのパスを画像に合わせて切り取る必要があります。複数の画像にまたがって線が描かれた場合にも、それぞれの画像に合わせてパスを切り取ります。

線が引かれる度に、ペンが通過したそれぞれの画像に対してはさみのアルゴリズムを実行する必要があります。60FPSでこれを実行するには素早い処理が必要となります。各画像の境界線ははさみで切られた時のみ変化するため、ペンによるクリッピングに備えて可能な限り境界線の情報をキャッシュしておき、コストを削減することが重要です。

どのくらい役に立つのか？

PerformanceBezierにマクロを追加したので、時間も比較することができます。このフラグをオンにすることで、同じ情報を取得するCGPathApplyの起動をシミュレーションできます。つまり、[path firstPoint]はO(1)ではなくO(N)になります。

初代iPad miniでキャッシュせずにPerformanceBezierを起動してみると、FPSが劇的に落ちます。メインスレッドで合計どのくらいの時間がかっかったのか、またそのうちどのくらいの時間がキャッシュしていないベジェのオペレーションに費やされたのかを測定するために道具を使ってみました。

テスト： ページ上に不規則にカットされた4つの画像を落とし、ペンでその画像の上をなぞってみます。新しいストロークセグメントが複数のパスに切り取られるたびにベジェのクリッピングアルゴリズムに負荷をかけます。

驚く結果が表示されました。線を描いているときにメインスレッドに費やされる時間は10秒間だったのですが、そのうち5秒の無駄な時間がキャッシュ可能なメソッドに費やされていることが分かりました。 言い方を変えると、Loose Leafではパフォーマンスが2倍になることになります。 最適化すれば、同じ時間でクリッピングを2回行うことができます。いくつかのメソッドでは、10倍速に向上されます。確かに有効性はアルゴリズムやコードにどのくらいUIBezierPathを使用するかによって異なりますが、これらの最適化なしでは、Loos Leafは実現できません。

コードの入手

ダウンロードとコードの閲覧： https://github.com/adamwulf/PerformanceBezier 。これは、私が公開した最初のリポジトリではありません。 この他にもLoose Leafにはたくさんのコードを公開しています 。今後さらに公開していく予定です。
現在、オープンソースではさみツールに関連するクリッピングパスのコードを公開するために作業を行っており、最初のステップを本日開始しました。今後をぜひ楽しみにしていてください！