この記事は、ラスタライザライブラリがどのように機能するかを知りたいだけの人にとって興味深いものです。
SVG形式のベクターフォント
ラスタライザーを作成するには、最初にベクターフォントの動作を理解する必要があります。 SVGはXMLに基づいており、おそらく人間にとって最も読みやすく理解しやすいため、SVGをメインのフォント形式として選択しました。
私が研究のために取った最初のフォントは、DejaVu Sans Mono Boldです。 内部から見た様子は次のとおりです。
<？xml version = "1.0" standalone = "no" ？>
<！DOCTYPE svg PUBLIC "-// W3C // DTD SVG 1.0 // EN" "http://www.w3.org/TR/2001/REC-
SVG-20010904 / DTD / svg10.dtd ">
<svg xmlns = " www.w3.org/2000/svg" width = "100％" height = "100％" >
<定義 >
<font horiz-adv-x = "1233" > <font-face
font-family = "DejaVu Sans Mono"
units-per-em = "2048"
panose-1 = "2 11 7 9 3 6 4 2 2 4"
上昇 = "1901"
降下 = "-483"
アルファベット = "0" />
<グリフ unicode = "" グリフ名 = "スペース" />
<グリフ unicode = "$" グリフ名 = "ドル" d = "M 694 528 V 226 Q 757 235 792 274 T
827375 Q 827437793476 T 694528 Z M 553 817 V 1100 Q 491 1092 460 1059 T 428
967 Q 428910459872 T 553 817 Z M 694-301 H 553 L 552 0 Q 465 3370 26 T 172
92 V 354 Q 275293371 260 T 553226 V 555 Q 356
594 260 689 T 164942 Q 164 1109 266 1208 T 553 1319 V 1556 H 694 L 695 1319 Q
766 1315 842 1301 T 999 1262 V 1006 Q 937 1046 861 1070 T 694 1100 V 793 Q 891
762 991 659 T 1092 383 Q 1092 219 984 114 T 695 0 L 694-301 Z " />
<！-...省略....->
<グリフ unicode = "〜" グリフ名 = "asciitilde" d = "M 1145 811 V 578 Q 1070 518 999
491 T 848 463 Q 758 463 645 514 Q 623 524 612 528 Q 535 562 484 574 T 381 586 Q
303586233557 T 88465 V 694 Q 166755239782 T 395809 Q 448809 498 798 T
622756 Q 633 751 655 741 Q 771 686 864
686 Q 934 686 1003 716 T 1145 811 Z " />
</フォント>
</ defs >
</ svg >
SVG形式の主要な部分はパスです。 ほとんどの画像情報を保存します。 輪郭タグは次のようになります。
<path d=" M 1145 811 V 578 Q 1070 518 999 491 T 848 463 Q 758 463 645 514 Q 623 524 612 528 Q 535 562 484 574 T 381 586 Q 303 586 233 557 T 88 465 V 694 Q 166 755 239 782 T 395 809 Q 448 809 498 798 T 622 756 Q 633 751 655 741 Q 771 686 864 686 Q 934 686 1003 716 T 1145 811 Z " id="path4840" style="fill:#000000;stroke:#000000;stroke-width:1px;stroke- linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
スタイルは塗りつぶしとストロークの色を記述し、 idはパスの名前を示し、 dはパス自体です。
やめて...ちょっと待って！ フォントのグリフタグ ：
<glyph unicode="~" glyph-name="asciitilde" d=" M 1145 811 V 578 Q 1070 518 999 491 T 848 463 Q 758 463 645 514 Q 623 524 612 528 Q 535 562 484 574 T 381 586 Q 303 586 233 557 T 88 465 V 694 Q 166 755 239 782 T 395 809 Q 448 809 498 798 T 622 756 Q 633 751 655 741 Q 771 686 864 686 Q 934 686 1003 716 T 1145 811 Z " />
ここにある。 文字（グリフ）の形状は、SVGの輪郭とまったく同じ方法で記述されます。 いっぱい
パラメータdの説明は仕様書にあります。簡単な説明を以下に示します。
x_prevおよびy_prev-前の点の座標
xc_prevおよびyc_prev-前の制御点の座標
グリフの概要と初期ラスタライズ
ベジェ曲線を出力し、SVGパスタグのコマンドをこのライブラリのコマンドに変換するライブラリを手元に用意しておくと、グリフのオフライン（ストローク）を簡単かつ迅速に取得できます。
ベクターグリフがあり、画面はラスターです。 つまり、オフラインで出力するタスクは、一連のセグメントとベジェ曲線からピクセルの配列を取得することです。 セグメントをピクセルに変換するのは非常に簡単です。多くのアルゴリズムがあり、それらは優れており、異なっています。
ベジェ曲線の場合、開始点（xz0、yz0）、終了点（xz2、yz2）、および制御点（xz1、yz1）の座標によって曲線の多くの点を見つけることができます。 これは次のように行われます。
for (step=0;step<10;step++) { t=step/10; bx[step]=(1-t)*(1-t)*xz0+2*t*(1-t)*xz1+t*t*xz2; by[step]=(1-t)*(1-t)*yz0+2*t*(1-t)*yz1+t*t*yz2; }
結果として、ベジエ曲線に属する点の10座標の配列があります。 微分方程式の複雑なシステムの曲線の長さに応じて、曲線を分割するポイントの数（つまり、ステップの最大値）が見つかります。
ただし、ベジェ曲線をポイント単位でピクセルに変換するのは遅く、悪いです。 曲線の形状が複雑で長い場合、ポイント数の計算には非常に長い時間がかかります。 また、ポイントごとにベジェ曲線を描くと、これらのポイントが必要よりも少なくなると、オフライングリフにギャップができてしまい、受け入れられません。 したがって、ベジェ曲線はセグメントに分割されます。 セグメントの開始座標と終了座標は、曲線上にある点の座標として取得されます。 ほとんどの場合、この近似により良い結果が得られます。
セグメントの数を決定する方法は？ stepの最大値を開始座標と終了座標の差に比例させるだけで十分だと思います（たとえば、step =（xz2-yz2）/ 100）。 ちなみに、グリフの高さが32ピクセル未満の私が出会ったすべてのフォントについては、ベジェ曲線を2つのセグメントに分割するだけで十分です。
ラスタライザの結果は次のようになります。
グリフアウトラインの塗りつぶしは、ラスタライズのメインステージです
これはすべて良いことですが、画面には色で塗りつぶされた文字が表示されます。 だから、どういうわけかそれは可能ですか？ 既にラスタライズされた輪郭を埋めるためのアルゴリズムの改善に約2か月を費やし、最終的にこのアプローチは根本的に間違っていると確信しました。 ベクター画像を塗りつぶすには、ラスター塗りつぶしは適していません。
この楽しいタスクの解決策を探して、コンピューターグラフィックスに関するMIT OCW講義に出会いました。 3次元グラフィックス（つまり、三角形ポリゴン）のラスタライズに関する講義に興味がありました。 この方法の本質は次のとおりです。ベクター形式では、画面上に三角形ポリゴンの投影が作成され、その後、ベクター三角形が塗りつぶされました。 シェーディングは次のように実行されました。画面の領域が選択され、それを超えると三角形がはっきりと消えなくなり、この領域の各ポイントについて、それがこの三角形に属するかどうかが判断されました。 同じ講義では、スイープライン塗りつぶしメソッド（CairoとFreeTypeが使用）は推奨されていないと主張していますが、このメソッドについては後で詳しく説明します。
ポイントがグリフのアウトラインに属しているか、属していないかを判断する方法を学ぶことは残っています。 グリフのアウトラインは常に閉じています。 したがって、任意のポイントから任意の方向にレイを描画し、それがグリフアウトラインを奇数回横切る場合、そのポイントはグリフに属し、偶数の場合、グリフに属しません。
興味深いことに、この方法は、回路に自己交差または穴があっても機能します。 このアルゴリズムは教科書であり、その実装の1つは
など：
xp = new Array (10, 20, 30, 40); yp = new Array (30, 40, 20, 10); function inPoly(x,y){ npol = xp.length; j = npol - 1; var c = 0; for (i = 0; i < npol;i++){ if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) && (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) { c = !c;} j = i;} return c;}
ここで、 xpとypは、多角形の頂点の座標の配列です。 関数inPoly（x、y）
1または0を返します-ポイントはポリゴンに属しているかどうか。 我々ができることを考えると
グリフのアウトラインをセグメント（ポリゴンの側面）に分割してから、この関数
私たちにとって素晴らしい。
最も単純なラスタライザー
ここで、グリフをxpおよびyp頂点の配列に変換して、単純なラスタライザを作成できます。 配列に0〜2000の座標を持つセグメントを含めます。次に、
function simple(){ for (x=0;x<2000;x++) { for (y=0;y<2000;y++) { if (inPoly(x,y)>0) raster[x][y]=1;}}}
この最も単純な関数は、ラスタライズされたグリフ画像をラスタ[x] [y]配列に作成します。 画面に表示される結果は次のようになります（複数のグリフを順番に表示し、画像を約20倍に拡大しました）。
画面上の解像度が2000x2000ピクセルのグリフは、だれにも必要とされる可能性は低く、inPolyアルゴリズムは非常にゆっくりと処理します。 より小さなグリフを表示するには、次のようにします。
function simple(scalefactor){ for (x=0;x<2000/scalefactor;x++) { for (y=0;y<2000/scalefactor;y++) { if (inPoly(x*scalefactor,y*scalefactor)>0) raster[x][y]=1;}}}
scalefactor = 2の場合、グリフは1000x1000ピクセルの正方形で表示され、scalefactor = 100の場合、20x20の正方形で表示されます（スクリーンフォントの通常のサイズ）。
このラスタライザは、最もシャープな（そして最も不均一な）輪郭を表示し、他のラスタライザよりもヒントとカットオフの制御アルゴリズムが必要です（解像度に応じて輪郭の形状を変更します）。 1つのラスタライズされたグリフをメモリに保存するには、x * y / 8バイトが必要です。 ASCII文字の完全なセットは、メモリ内でx * y * 32バイトを超えません（10x10フォントの場合は3200バイト、16x16フォントの場合は8192バイト）。 ラスタライズプロセスは、ポイント* 2 * 4バイトより少し多くのメモリを使用します（ポイントはグリフ内のポイント数で、ポイントは通常100未満、場合によっては10未満です）。
アンチエイリアス（スムージング）
スムージングを使用したラスタライズは、はるかに優れた結果をもたらします。 使用されるFreeType 1ライブラリ
5ハーフトーンアンチエイリアシング、FreeType2はより実質的なものを使用します（10および17ハーフトーンアンチエイリアシング、詳細には触れませんでした）。 実験してみると、10階調の平滑化は5階調よりもはるかに優れていると確信しました。
function aadraw(scalefactor){ // (3*3) , for (x=0;x<size*3/scalefactor;x++) { for (y=0;y<size*3/scalefactor;y++) { if (inpoly(x*scalefactor/3,y*scalefactor/3)>0) landscape[x][y]=1;}} // for (x=0;x<size/scalefactor;x++) { for (y=0;y<size/scalefactor;y++) { // , 00 FF color[x][y]=255-28*(landscape[x*3][y*3]+landscape[x*3][y*3+1]+landscape[x*3][y*3+2]+landscape[x*3+1][y*3]+landscape[x*3+1][y*3+1]+landscape[x*3+1][y*3+2]+landscape[x*3+2][y*3]+landscape[x*3+2][y*3+1]+landscape[x*3+2][y*3+2]));}}// }//
ここで、サイズはグリフのサイズです（単純なラスタライザーでは、サイズの代わりに2000を置き換えました）。 ランドスケープ配列は中間データを格納するために使用され、最終結果はカラー[x] [y]バイト配列に格納されます。
サブピクセルスムージング
サブピクセルアンチエイリアスは、多くの場合、LCDモニターにフォントを表示するために使用されます。 従来のモニターでは、サブピクセルスムージングの結果は通常のスムージングとほぼ同じですが、LCDでは、サブピクセルによるスムージングにより、水平解像度を3倍に増やすことができます。 この方法の本質は次のとおりです。人間の目は、陰影よりも強度を区別します。 詳細は多くのソースにあり、 ロシアのウィキペディアのページでさえ、実用的な使用には説明で十分です。
単純なサブピクセルアンチエイリアシングの問題は、出力の画質が10階調のアンチエイリアシングアルゴリズムの画質よりも低いことです。 品質を向上させるために、垂直方向に4ハーフトーンのスムージング、水平方向にサブピクセルのスムージングを使用します。 ディレクトリからのサブピクセルスムージングアルゴリズムは、ここでそのようなひどい結果を与えます：
マルチカラーの「汚れ」を取り除くために、ぼかし係数を次のように変更しました
水平方向に加えて、わずかに色域を変更しました。 結果は次のようになります（最高
LCDモニターで表示すると品質が達成されます）：
function xdraw(scalefactor){ // (3*2) , for (x=0;x<size*3/scalefactor;x++) { for (y=0;y<size*2/scalefactor;y++) { if (inpoly(x*scalefactor/3,y*scalefactor/2)>0) landscape[x][y]=1;}} // for (x=0;x<size*3/scalefactor;x++) { for (y=0;y<size*2/scalefactor;y++) { if (x>2 && x<size*3/scalefactor-2) landscape1[x][y]=landscape[x-2][y]*(1/9)+landscape[x+2][y]*(1/9)+landscape[x-1][y]*(2/9)+landscape[x+1][y]*(2/9)+landscape[x][y]*(1/3)}} // , for (x=0;x<size*3/scalefactor;x++) { for (y=1;y<size/scalefactor;y++) { landscape2[x][y]=landscape1[x][y*2-1]*(2/9)+landscape1[x][y*2+1]*(2/9)+landscape1[x][y*2]*(4/9); if (landscape2[x][y]==8/9) landscape2[x][y]=1;}} // // for (x=0;x<size/scalefactor;x++) { for (y=0;y<size/scalefactor;y++) { r[x][y]=Math.floor(255-255*landscape2[x*3][y]);g[x][y]=Math.floor(255-255*landscape2[x*3+1][y]);b[x][y]=Math.floor(255-255*landscape2[x*3+2][y]);}} }//
スイープライン方式 主なアイデア
もう一度話したinPolyアルゴリズムを見てみましょう。 動作しますが、大きな文字では動作が遅くなります。 なんで？ 処理速度は正方形のサイズに比例するためです。 サイズは2倍になり、速度は4倍に減少し、サイズは4倍に増加しました。速度は16倍に低下しました。
アルゴリズムを少し見て考えてみると、並べ替えた各ポイントについて、水平光線が放出され、輪郭との交点が決定されることがわかります。 一連の計算が無駄に行われることがわかります。同じY座標を持つすべてのポイントについて、これらのポイントを通過する水平線の方程式は同じになります。
以前は、各ポイントの光線を見つけ、それが輪郭を横断する回数をカウントしました。 交差点の座標は見つかりましたが、保存しませんでした。 そして、これを試してみましょう。点（0、y）のみの光線を見つけ、光線と等高線の交点の座標を保存します。
注意してください：
1）輪郭の一部が水平で掃引線と一致する場合、輪郭のこの部分との交差は考慮されません。
2）回路が閉じているため、1回の掃引では常に偶数の交点が検出されます。
残っているのは、奇数ポイントと偶数ポイントの間のスペースを埋め、偶数と奇数の交点の間のスペースを残すことです（線を左から右に渡すとき）。 フォントは適切に設計する必要があり、グリフの解像度は小さくてはなりません。そうすれば、品質は低下しません。
速度を比較します。 私たちの古いアルゴリズムは、9x9ポイントから光線を放出し、輪郭との交点の座標を見つけることでした。 新しいアルゴリズムは9本の光線しか放出しませんでした。つまり、1桁速く動作します。 同時に、掃引線アルゴリズムは、私たちが持っていたアルゴリズムに非常に近いものです。
スイープライン。 InPolyコードの変更
したがって、inPoly関数があります。 スイープ関数を作成しましょう。
function inPoly(x,y){ npol = xp.length; j = npol - 1; var c = 0; for (i = 0; i < npol;i++){ if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) && (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) { c = !c;} j = i;} return c;}
明らかに、入力パラメーターxは不要になりました。 入力スイープ関数は、現在の行番号のみを取得します。 ただし、入力パラメーターのスケールは便利です。目的のスケールでxをすぐに取得できます。
現在の掃引線と直線の輪郭の交点のx座標は、次のように見つかりました。
(x >(xp[j]- xp[i])*(y - yp[i])/(yp[j]- yp[i])+ xp[i]))
つまり、次のようになります。
x =(xp[j]- xp[i])*(y - yp[i])/(yp[j]- yp[i])+ xp[i])
関数の出力で、交点の座標から配列を取得する必要があります。 この配列の長さを知っておくといいでしょう。 したがって、c =！Cではなくc ++になります。
その結果、次のようになります。
function sweep(y,scale){ npol = xp.length; // .... j = npol -1; var c =0; for(i =0; i < npol;i++){ if(((yp[i]<=y)&&(y<yp[j]))||((yp[j]<=y)&&(y<yp[i]))) { x =(xp[j]- xp[i])*(y - yp[i])/(yp[j]- yp[i])+ xp[i]; curline[c]=x/scale; c++;} // , j = i;} return c;} //
そして再び-シンプルなラスタライザー
そのため、各行に対してスイープを呼び出し、スイープラインの交点を見つけ、これらの交点で配列を埋めます。 ただし、スイープ関数は、たとえば次のような座標の配列を返すことができます。
14、8、16、7
輪郭を正しく埋めるには、線（7、y）-（8、y）および（14、y）-（16、y）で輪郭を埋める必要があります。 つまり、スイープ関数の結果を並べ替える必要があります。 クイックソートはうまく機能し、多数の座標を使用することをお勧めします。 ただし、手元にあるフォントの場合、カリーン配列には基本的に2〜8個の交差座標があり、生活を複雑にしないために、バブルソートを使用しました。 私のバブル関数は、入力として配列とその長さを受け入れ、明示的に何も返しませんが、配列はソートされます。
ラスタライザーに直接進みます。 最初に各行に対してスイープを呼び出す必要があり、次にバブルコマンドを使用して曲線配列を並べ替えます。
for(y=0;y<size/scale;y++){ // x every=sweep(y*scale, scale); //every — bubble(curline,every); // for(point=0;point<every;point=point+2){ // for(x=curline[point];x<curline[point+1];x++){landscape[x][y]=1;} // }}//
配列は0から始まるので、curline [0 + x]からcurline [1 + x]に線を引く必要があります。 以上です。 ランドスケープアレイを取得しました。以前と同じように作業する必要があります。 つまり、その後、アンチエイリアスまたはサブピクセルスムージング、あるいはその両方によってスムージングできます。 主なことは、スケールがスイープ関数にも転送されるという事実に注意を払うことであり、水平方向の拡張を決定します。
作業結果
これで、ベクターフォントのラスタライザーを自分の手で作成する方法がわかりました。 ラスタライザーの実際のサンプルはここからダウンロードできますが、Hummingbirdオペレーティングシステム用に記述されています（したがって、このサンプルを実行する場合はダウンロードする必要があります）。 コンパイルされたプログラムのサイズは2589バイトで、RAMの最大使用量は約300キロバイトです。 そして、これは制限ではありません！