ベクトル画像をラスター化する一般的なアルゴリズムは何ですか？線、円、ベジェ曲線などのプリミティブをラスター化するアルゴリズムをたくさん見つけました。しかし、一般的には、どうすればよいですか？単純に、ベクター画像の各ベクター図形に移動し、そのピクセルを取得してラスターイメージに配置しますか？または、他の何か？
そして別の質問ですが、並行性を使用して処理時間を改善するにはどうすればよいですか？たとえば、ベクターフィギュアを分離し、同時にそれらのピクセルを取得することができます。しかし、おそらくこれを行う他の方法がありますか？
一般的なラスタライズアルゴリズムは、画像内のポリゴンごとにこれです。
（ポリゴンは、直線セグメントとパラメトリックスプラインから作成された1つ以上の閉じた曲線として定義されます。通常、これらは2次（円錐曲線の2次）と3次（3次）のベジエスプラインです。これらの閉じた曲線は、次のように定義されます。曲線がトラバースされるとき、内側は常に左側にあります。したがって、通常の形状は反時計回りに実行され、穴は時計回りに実行されます。）
（i）（投影）ポリゴンをデスティネーションビットマップと同じ座標系に変換します。解像度は同じである必要はなく、アンチエイリアス処理された画像の場合、多くの場合、より高くなります。たとえば、FreeTypeは64分の1のピクセルを使用します。
（ii）（Yで単調にする）必要に応じて、ポリゴンの各セグメントを、連続的に上向きまたは下向きに走る小さなセグメントに分割します。このステージは曲線セグメントにのみ必要であり、ベジェスプラインを使用する場合は比較的簡単です。通常の方法は、単調性が達成されるまで繰り返し二等分することです。すべての水平セグメントを破棄します。
（iii）（実行制限をマークする）各セグメントを一時的なビットマップに描画します。直線にはブレゼンハムのアルゴリズムを使用します。曲線の場合、線が実際の曲線から（たとえば）1/8ピクセル以内になるまで二等分し、最初から最後まで直線を使用します。描画するときは、ピクセルに何らかの方法でマークを付けて、（a）実行の開始か終了かを示します。下向きの線は開始で、上向きの線は終了です。（b）カバレッジ-形状の内側にあるピクセルの割合。これは、アルゴリズムの詳細が異なり、ワインディングルール（非ゼロと偶数奇数）が区別される場所です。
（iv）（スキャン）一時ビットマップを行ごとにトラバースします。各行について、左から右にスキャンします。たとえば、ビットマップに格納されている数値を格納されている数値に加算することにより、現在の位置が図形の内側にあるかどうかを示す状態を維持します。単純なモノクロラスタライズでは、前の段階で書き込まれたこの数値は、エッジをシェイプに交差させるときに+1になり、シェイプから出るときに-1になります。同じ状態のピクセルの実行を累積します。ランを描画モジュールに送信します。たとえば、FreeTypeは、Y座標、開始X座標と終了X座標、および0〜255のカバレッジで構成されるランを出力します。描画モジュールは、現在の描画色に適用されるアルファ値としてカバレッジを使用できます。 、またはテクスチャに適用されるマスクとして。
上記は非常に単純化されていますが、一般的な考え方を示しています。
ほとんどのオープンソースプログラムは、次のプロジェクトのいずれかから派生したラスタライズコードを使用します。
FreeType-スタンドアロンで比較的使いやすいモノラルとアンチエイリアシングの両方のラスタライザモジュールを含むフォントラスタライザ-つまり、フォントだけでなく、あらゆる形状に対応します。私はこのシステムをいくつかの商用ポータブルC++プロジェクトでうまく使用しました。
FreeTypeのシステムは、RaphLevienのLibartに触発されました。
Anti-Grainは、もう1つの人気があり影響力のあるC++ライブラリです。
Kiia Kallioによって実装されたスキャンラインエッジフラグシステムもあります。これは有望に見え、Anti-Grainよりも高速であるように見えます。
これらのライブラリのすべてではありませんが、ほとんどの場合、2次および3次のベジエスプラインと直線セグメントから作成された形状を受け入れます。そうでないもの（例えば、K。Kallioのライブラリ）は、まっすぐなエッジのポリゴンのみを取ります。しかし、実際の曲線からの望ましい最大距離よりも近い一連の線分に曲線を「平坦化」するのは非常に簡単です。FreeTypeはそれを内部的に行い、そのコードは必要に応じて借りることができます。