PixelSortの高速化

ピクセル・ソートはキム・アセンドルフ（アーゼンドルフという日本語表記もある）による手法でありソースコードも公開されています。

処理が重たかったので高速化をしてみました。

ソートアルゴリズムについて

速くて安定してしているので、おとなしくstd::sortを使いましょう。アルゴリズム的にはquicksort with tail recursion eliminationみたいです。

ピクセルソートの処理の並列化

ピクセルソートは画像の行（または列）を一つの単位として処理しています。この処理は行を超えることがなく独立しており、簡単にマルチスレッド化することできます。

dispatch_group_t group = dispatch_group_create();
dispatch_queue_t queue = dispatch_get_global_queue(
    DISPATCH_QUEUE_PRIORITY_HIGH,0
);

dispatch_group_async(group,queue,^{ this->pixelsort[0]->sort(this->pixel); });
dispatch_group_async(group,queue,^{ this->pixelsort[1]->sort(this->pixel+this->offset); });
dispatch_group_async(group,queue,^{ this->pixelsort[2]->sort(this->pixel+this->offset*2); });
dispatch_group_async(group,queue,^{ this->pixelsort[3]->sort(this->pixel+this->offset*3); });
dispatch_group_async(group,queue,^{ this->pixelsort[4]->sort(this->pixel+this->offset*4); });
dispatch_group_async(group,queue,^{ this->pixelsort[5]->sort(this->pixel+this->offset*5); });
dispatch_group_async(group,queue,^{ this->pixelsort[6]->sort(this->pixel+this->offset*6); });
dispatch_group_async(group,queue,^{ this->pixelsort[7]->sort(this->pixel+this->offset*7); });
dispatch_group_async(group,queue,^{ this->pixelsort[8]->sort(this->pixel+this->offset*8); });

dispatch_group_wait(group,DISPATCH_TIME_FOREVER);

ピクセルソートの処理高速化（縦方向）

ピクセルソートをマルチスレッド化することによって高速化されましたが、縦方向のピクセルを処理をする際に、メモリジャンプが発生しキャッシュメモリが効かず横方向に比べて処理時間がかなりかかります。そのためメモリの方向を横方向に順序を変更する必要があります。この変換を行うときにMSLをつかってメモリの順序を変更するのがベターでした。replaceRegion:mipmapLevel:withBytes:bytesPerRow:を使い縦方向にピクセルソートをかけたピクセルデータをテクスチャに書き込み、シェーダで縦方向のピクセル順に変更して、METAL-NYUMONにも書いたgetBytes:bytesPerRow:fromRegion:mipmapLevel:を使い順序が置換されたピクセルデータとして読み出します。こうすることで縦方向の処理を横方向のピクセルソートとして行えます。

縦方向のピクセル順へと変更した画像

画面に表示する際にピクセル順を再度シェーダで戻せば完成です。入力画像や、ピクセルソートの閾値にもよりますが1920x1080の解像度（MacBook Pro 13-inch, 2017 without Touch Bar）で30fps出ています。