ラスタリングベクター画像の一般的なアルゴリズム

Question

ラスター化ベクトル画像の一般的なアルゴリズムは何ですか？ライン、サークル、ベジエ曲線などのプリミティブをラスター化するアルゴリズムがたくさんありましたが、一般的にはどうすればよいですか？簡単には、ベクトル画像のベクトル図に移動し、ピクセルを取得してラスターイメージに入れますか？または、他の何か？

また、別の質問は、並行性を使用して処理時間を改善するにはどうすればよいですか？たとえば、ベクターの数値を分離し、同時にピクセルを取得できます。しかし、これを行う他の方法があるかもしれませんか？

Answer 1

一般的なラスター化アルゴリズムは、画像内の各ポリゴンについてです。

（ポリゴンは、直線セグメントとパラメトリックスプラインから作られた1つまたは複数の閉じた曲線として定義されます - 通常の練習では、これらは2次（Conicエイリアス二次）および3次（キュービック）Bézierスプラインです。これらの閉じた曲線は定義されています。曲線が通過するため、内側は常に左側にあります。したがって、通常の形状は反時計回りに実行され、穴は時計回りに実行されます。

（i）（投影）ポリゴンを宛先ビットマップと同じ座標系に変換します。解像度が同じである必要はありません。アンチアライア化された画像の場合、多くの場合、より大きくなります。たとえば、Freetypeは64分の1のピクセルを使用します。

（ii）（yで単調にする）必要に応じて、ポリゴンの各セグメントを連続的に上または下向きに走る小さなセグメントに分割します。この段階は、湾曲したセグメントにのみ必要であり、Bézierスプラインを使用する場合は比較的簡単です。通常の方法は、単調性が達成されるまで繰り返し二分することです。すべての水平セグメントを廃棄します。

（iii）（実行制限をマーク）各セグメントを一時的なビットマップに引き込みます。直線にBresenhamのアルゴリズムを使用します。曲線の場合は、ラインが実際の曲線からピクセルの1/8を超えないまで二等分してから、最初から最後まで直線を使用します。描画するとき、マークピクセルは何らかの方法で（a）実行の開始または終了かどうかを示すために、下向きの行が開始され、上向き線が終了します。 （b）カバレッジ - 形状の内側にあるピクセルの割合。これは、アルゴリズムが詳細と巻き上げ規則が異なる場所です（ゼロ以外 対 偶数）際立っています。

（iv）（スキャン）一時的なビットマップ、行ごとにトラバース。各行について、左から右にスキャンします。 （たとえば）ビットマップに保存されている数値を保存された数に追加することにより、現在の位置が形状の中にあるかどうかを示す状態を維持します。単純なモノクロラスター化では、前の段階で書かれたこの数値は、形状にエッジを渡るときに+1、形状から出るときは-1になります。同じ状態にピクセルの走行を蓄積します。描画モジュールに実行を送信します。たとえば、y座標、開始および終了x座標、および0から255までのカバレッジで構成されるフリータイプのエミットラン、またはテクスチャに適用されるマスクとして。

上記は非常に大きな単純化ですが、一般的なアイデアを提供します。

ほとんどのオープンソースプログラムは、次のプロジェクトのいずれかから導出されたラスター化コードを使用しています。

フリータイプ - 比較的使いやすいスタンドアロン - つまり、フォントだけでなく、あらゆる形状であるモノラスアンチエイジングラスター化装置モジュールを含むフォントラスターザー。このシステムは、いくつかの商用ポータブルC ++プロジェクトで正常に使用しました。

Freetypeのシステムは、Raph Levienのシステムに触発されました リバート.

アンチグレイン もう1つの人気のある影響力のあるC ++ライブラリです。

あります スキャンラインエッジフラグシステム Kiia Kallioによって実装されています。KiiaKallioは、有望に見え、抗穀物よりも速いようです。

これらのライブラリのすべてではありませんが、ほとんどの場合、すべてのライブラリは、直線セグメントだけでなく、2次および立方体のベジエスプラインから作られた形状を受け入れます。そうでないもの（たとえば、K。Kallioの図書館など）は、まっすぐなポリゴンのみを服用しています。しかし、実際の曲線からの目的の最大距離よりも、一連のラインセグメントに曲線を「平らに」することは非常に簡単です。 Freetypeは内部的にそれを行い、そのコードは必要に応じて借りることができます。