符号付き距離フィールドまたはラスターからベクターを作成する方法

今日は、距離マップ（符号付き距離フィールド）を使用した画像の生成に焦点を当てます。 このタイプの画像は、実際にはビデオアクセラレータで「ベクター」グラフィックを取得できるという点で注目に値します。 Valveは、2007年にスケーラブルデカール用にTeam Fortress 2でこのラスター化方法を提供した最初の1つですが、256x256ピクセルのみのテクスチャを使用して優れた品質のフォントをレンダリングできますが、まだあまり人気がありません。 この方法は、最新の高解像度画面に最適で、ゲームのテクスチャを大幅に節約できます。ハードウェアを必要とせず、スマートフォンで最適に動作します。



トリックは、特別に準備された距離マップを作成して、最も単純なシェーダーを使用する場合に理想的なベクトル図が得られるようにすることです。 さらに、シェーダーの助けを借りて、シャドウ、グロー、ボリュームなどの効果を得ることができます。

そのような画像を作成する方法は？ ImageMagickを使用すると、1つのコマンドでこれを実行できます。

convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png 

これに終止符を打つことはできますが、本格的なトピックは得られません。 さて、カットの下-高速SDF計算アルゴリズムの説明、C ++の例、およびOpenGLのいくつかのシェーダー。

その呪文は何でしたか？

この投稿の最初にある最初のコマンドは、白黒のラスターアウトラインからSDFを生成するためのレシピです。 ImageMagickの新しい機能であるMorphologyに基づいています。 形態変換の中には、距離マップの計算もあります 。

距離マップの計算は、最も単純なアルゴリズムです。 ピクセルが黒または白のモノクロ画像で機能します。 色の1つは内部色で、もう1つは外部色であると考えます（お好みで、この写真のチーターの黒いピクセルは内部色になります）。 背景色や前景色と呼ばれることもあります。 画像の「内部」ピクセルごとに、最も近い「外部」ピクセルを見つけ、このピクセルの輝度値を、最も近い「外部」ピクセルまでのユークリッド距離として設定する必要があります。 つまり、画像のすべての「外部」ピクセルまでの距離を計算し、最小のピクセルを選択する必要があります。 結果として得られる距離マップは距離フィールド（DF）と呼ばれますが、これまでのところ私たちには適していません。 SDF（Signed DF）を取得するには、画像を反転し、アルゴリズムを繰り返し、再度反転して前の結果に追加します。

強度値を距離値に正確に設定する必要はありません。必要に応じて「ぼやけた」画像を拡大縮小できます。 特に、鮮明な輪郭のレンダリングにはぼやけの少ないマップを使用することをお勧めします。シャドウやグローなどの特殊効果の場合は、距離マップを大きくすることをお勧めします。



ImageMagickはこのようなマップを作成するための最速かつ最も簡単な方法ではありませんが、ImageMagickはほとんどすべてのオペレーティングシステムに存在し、開発者がスプライトのパイプライン処理によく使用するため、これが最良のオプションだと思います。 スクリプトを少し完成させ、画像生成をストリームに配置するだけで十分です。

仕組みを見てみましょう。 モルフォロジー演算を単に画像に適用して適用するだけでは、最良の結果は得られません。

 convert nosdf.png -morphology Distance Euclidean sdf.png 

マレヴィッチ？ いいえ、 夜間に石炭を盗むだけで、十分なコントラストはありません。 -auto-levelパラメーターを使用すると、すぐに引き出すことができます。

 convert nosdf.png -morphology Distance Euclidean -auto-level sdf.png 

欠陥はすぐに明らかになります。距離マップは外部からのみ生成されます。 これは、アルゴリズム自体も2パスであるという事実の結果です。ネガティブについても同じことを繰り返します。

 convert nosdf.png -negate -morphology Distance Euclidean -auto-level sdf.png 

今反対の状況-外に十分なカードがありません。

中間層を使用してこれらの2つのアルゴリズムを組み合わせ、コントラストを強化し、投稿の最初から猛烈なスクリプトを取得することが残っています。

 convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png 

いくつかの説明：
-resize 400% -元の画像を増やして、ぎざぎざのエッジを除去します。 このアルゴリズムは白黒画像に対してのみ機能し、少なくとも何らかの形でアンチエイリアスを検討したいと思います。 ただし、オリジナルを4回以上手元に置くことを常にお勧めします。 たとえば、Valveは、デモ用に4Kイメージを使用し、そこから64x64 SDFを受け取ります。 もちろん、これはすでに多すぎます。 8：1の比率が許容範囲内であることがわかりました。
- -level 45%,55% -距離マップのぼかしの度合いを調整できます。デフォルトでは、すでに非常にあいまいです。
-filter Jincおよび-threshold 30% -実験的に、このフィルターとしきい値は元の画像に最適です。 ネタバレの下で、確認したい人のためのスクリプトとソース。


さて、より高い解像度のオリジナルがある場合、ズームインしてトリックを使わずに、すでに小さい側にのみスケーリングすることができます：

 convert in.png -threshold 50% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -filter Jinc -resize 10% out.png 

Jincフィルターは、マップのサイズを縮小しながらサンプリングの品質を向上させることを目的としているため、チェーンの最後に「移動」したことに注意してください。 また、 -threshold 50%削除しないでください-ユークリッドは、非モノクロ画像では正しく機能しません。

議論の余地のある問題 。

コントラストを「伸ばす」ことは理にかなっていますか？ 一般に、理論的には、コントラストが増加すると、サンプルのデルタが増加し、そこからハードウェア補間法を使用してアンチエイリアスが計算されます。 要するに、特に明確で滑らかな輪郭と影のような効果はそれほど重要ではない場合、ストレッチする必要があります。 元のカードが伸びるだけでなく縮む場合は、あまり持ちすぎないようにしてください。そうしないと、画像を縮小すると、SDFのぼやけたエッジのためにアンチエイリアスが悪化します。

品質はSDFカードの解像度にどのように依存しますか？ PSNRをマップの解像度とコントラストに対してプロットしようとしました。 一般に、品質は向上しますが、それでもカードのコントラストに依存します。 チャートの依存関係を評価できます。


ここで、スケールはソース、レベルのパーセンテージとしてのスケールです-コントラストがどれだけ「引き伸ばされた」か。 スケールへの依存性はあまり線形ではなく、30％が非常に妥協的なオプションであり、コントラストが輪郭の品質にかなり強く影響すると結論付けることができます。

ユークリッドフィルターのサイズは品質にどの程度影響しますか？ フィルターサイズを大きくすると、0.1 dB +の増加になります。これは、私の意見では重要ではありません。

元の画像をどれだけ「縮小」できますか？ 形状に大きく依存します。 SDFは鋭い角が好きではなく、この例のチーターのような滑らかな絵は、ミニチュアスケールでも素晴らしい感じがします。

C ++での高速アルゴリズムの実装

アルゴリズムは単純ですが、その「額」の実装は数時間機能します。実際、各ピクセルの画像全体をスキャンする必要があります。 O（N ^ 2）は、私たちにはまったく適していません。 しかし、頭のいい人たちは、O（N）で機能する正確な（！）DF計算のためのアルゴリズムをすでに考え、思いついています。 タスクをSDFに拡張することは、非常に簡単です（前の例を参照）。

一番下の行。 各ピクセルの距離をカウントする代わりに、特定の条件下で単純に距離を増やしながら、画像を2回連続して通過します。 これは、高速のBox-Blurアルゴリズムを連想させます。 Matanは[2]から収集できますが、指で説明しようとします。

ピクセルpを、元の画像で構成される配列N * Mの要素と呼びます。 ピクセルは次の構造です。

 { x, y -    f -    } 

ご覧のとおり、明るさなどについては何もありません。 -それは必要ありません。 配列は次のように形成されます。
元の画像のピクセルが明るい場合、

 x = y = 9999 f = 9999 * 9999 

元の画像のピクセルが暗い場合、

 x = y = f = 0 

各ピクセルには8つの近傍があり、次のように番号を付けます。

 2 3 4 1 p 5 8 7 6 

次に、2つの補助機能を紹介します。 関数hは、ピクセルと隣接ピクセル間のユークリッド距離を計算するために必要です。関数Gは、コンポーネント間の新しい距離値を計算するために使用されます。

 h(p, q) { if q -  1  5 {return 2 * qx + 1} if q -  3  7 {return 2 * qy + 1}    {return 2 * (qx + qy + 1)} } 

 G(p, q) { if q -  1  5 {return (1, 0)} if q -  3  7 {return (0, 1)}    {return (1, 1)} } 

最初のパス 。 このパッセージは、画像の左上から右下に向かって順番に実行されます。 擬似コード：

    p  {    q  1  4 { if (h(p, q) + qf < pf) { pf = h(p, q) + qf (px, py) = (qx + qy) + G(p, q) } } } 

セカンドパス 。 このパスは逆の順序で実行されます（画像の右下から左上へ）。 擬似コード：

    p  {    q  5  8 { if (h(p, q) + qf < pf) { pf = h(p, q) + qf (px, py) = (qx + qy) + G(p, q) } } } 

元の画像のネガに対してアルゴリズムを繰り返す必要があります。 次に、受け取った2枚のカードについて、最終的な距離の計算と減算を行って、2枚のDFカードを1つのSDFに結合する必要があります。

 d1 = sqrt(p1.f + 1); d2 = sqrt(p2.f + 1); d = d1 - d2; 

最初に、構造内でユークリッド距離の正方形を維持したため、ルートを研磨する必要があります。 なぜ追加する必要があるのですか？質問しないでください。結果は経験的で、曲がっていない場合があります:)最終的なSDFカードは、最初から2番目を引いた結果です。その後、必要に応じて値をスケーリングする必要があります。

私の意見では、それがどのように機能するかを指で説明しようとしても非常に混乱しているように見えるので、C ++でソースコードを提供します。 入力画像として、プロセスの可視性を損なわないように、QtのQImageを使用しました。 ソースはソース[3]に基づいていますが、バグがあります。



ここでは、両方のパスで1ピクセル幅の「ウィンドウ」を使用するため、元の画像の周囲に1ピクセルの境界線を追加して、境界線をチェックしないようにします。 負の場合、境界も反対の値に変更する必要がありますが、これは[3]で考慮されていませんでした。

完全に機能するアルゴリズムは、オープンソースのラスターフォントジェネレーターUBFGにあります。 結果の例：

シャデリム

（SDFからラスターコンターへの）逆変換の考え方は、ぼやけたエッジが見えなくなる程度にコントラストを上げることに基づいています。 SDFのコントラストを変更すると、さまざまな効果を得ることができ、画像のアンチエイリアスの品質を調整できます。 例として、ソースを取り上げます。



これもSDFであり、非常に圧縮され、サイズが小さくなっています。 16倍に増やしましょう。



さて、美しい輪郭を得るには、コントラストを上げます。 これらの目的でGIMPを使用しました。



SDFをリアルタイムで使用した結果を確認するには、シェーダーが不可欠です。 最も単純なアルファテストも使用できますが、そのルートでアンチエイリアスをカットします。 ただし、使用されるシェーダーはほんの2、3の命令であり、実際にはパフォーマンスには影響しません。 さらに、シェーダーは現在安価であり、メモリ/キャッシュは高価であることを考慮すると、ビデオメモリを節約することにより、高速化を実現できます。

次に、このビジネスをOpenGLで使用する方法を見てみましょう。 すべての例は、純粋なGLSLソースコードとして提供されます。 任意のシェーダーエディターで試すことができます。 テクスチャをロードできる唯一のエディターであるため、 Kick.jsエディターですべての例をテストしました。

最も簡単なクイックオプション

 precision highp float; uniform sampler2D tex; const float contrast = 40.; void main(void) { vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.3).xxx; gl_FragColor = vec4((c-0.5)*contrast,1.0); } 

ここでは、平均値（0.5）に対するコントラストを描画します。 コントラストの強さは、テクスチャのスケールとDFマップのスミアによって異なります。パラメータは実験的に選択され、スケール係数を使用して均一に設定されます。

smoothstepフィルターを使用すると、品質をわずかに改善できます。

 precision highp float; uniform sampler2D tex; const float threshold = .01; void main(void) { vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.3).xxx; vec3 res = smoothstep(.5-threshold, .5+threshold, c); gl_FragColor = vec4(res,1.0); } 

ここで、しきい値も選択する必要があります。 smoothstep古いグラフィックカードや携帯電話でsmoothstep少し遅くなります。

アウトライン効果

この効果を得るには、2つのしきい値を取得し、色を反転する必要があります。

 precision highp float; uniform sampler2D tex; const float contrast = 20.; void main(void) { vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35).xxx; vec3 c1 = (c-.45) * contrast; vec3 c2 = 1.-(c-.5) * contrast; vec3 res = mix(c1, c2, (c-.5)*contrast); gl_FragColor = vec4(res,1.0); } 

結果：

グローとシャドウ効果

前の例を少しpohimichit-私たちはグロー効果を取得します：

 precision highp float; uniform sampler2D tex; const float contrast = 20.; const float glow = 2.; void main(void) { vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35).xxx; vec3 c1 = clamp((c-.5)*contrast,0.,1.); vec3 c2 = clamp(1.-(c-.5)/glow, 0., 1.); vec3 res = 1.-mix(c1, c2, (c-.5)*contrast); gl_FragColor = vec4(res,1.0); } 

影を付けるには、オフセット付きのグローの色を使用する必要があります。

 precision highp float; uniform sampler2D tex; const float contrast = 20.; const float glow = 2.; void main(void) { vec3 c = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35).xxx; vec3 gc = texture2D(tex,gl_FragCoord.xy/vec2(256., 128.)*.35 + vec2(-0.02,0.02)).xxx; vec3 c1 = clamp((c-.5)*contrast,0.,1.); vec3 c2 = clamp(1.-(gc-.5)/glow, 0., 1.); vec3 res = 1.-mix(c1, c2, (c-.5)*contrast); gl_FragColor = vec4(res,1.0); } 

結果：


結果はそれほど暑く見えないかもしれませんが、これは小さすぎるマップを使用したためです。

参照資料

[1] ベクトルテクスチャと特殊効果のアルファテスト拡大の改善は、Valveの記事と同じです。
[2] フランク・Y・シー、イー・タ・ウー。 3x3近傍を使用した2回のスキャンでのユークリッド距離の高速変換 -中国語？ いいえ、ただのニュージャージー大学です。
[3] www.codersnotes.com/notes/signed-distance-fields-これもかなり高速なアルゴリズムですが、残念ながらその作成者はいくつかのエラーを起こし、乗算が存在します。これは、この記事で示したアルゴリズムよりわずかに遅いです。
[4] contourtextures.wikidot.comはSDF計算の別の実装ですが、その利点はエッジのスムージングを考慮して最も近いポイントを決定できることです。 パフォーマンスについては何も言われていませんが、高解像度のオリジナルを入手する方法がない場合は良いことです（一方で、高級なトリックを行うことができます）。 あなたがそれを使用した経験がある場合は、コメントで退会します。
[5] gpuhacks.wordpress.com/2013/07/08/signed-distance-field-rendering-of-color-bit-planes-カラーベクトル画像をレンダリングする方法（少数の色に適しています）。
[6] distance.sourceforge.netは、さまざまなSDF計算アルゴリズムが比較される興味深いリソースです。

upd 。 Bas1lによる発言のおかげで、アルゴリズムはまだ完全に正確ではなく、証明のエラーにより、最近傍までの距離の計算にエラーを与える可能性があります。 この記事では、アルゴリズムの改良版を紹介します。

upd2 ユーザーachkasovからシェーダーに関するコメント。 突然の移行が発生した場合、SDFカードに融合と不均一なアンチエイリアシングが現れることがあります。 効果とその対処方法の詳細： iquilezles.org/www/articles/distance/distance.htm

シェーダーを変更すると、エリア、ヘム、テールが大幅に改善されます。