【誤訳訂正書】
【提出日】平成20年1月11日(2008.1.11)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【書類名】明細書
【発明の名称】アウトラインフォントおよび他のグラフィック要素についてアンチエイリアシングを伴うスキャン変換を高速に実行するためのシステム
【特許請求の範囲】
【請求項１】
人間による読み取りが可能な表示に使用するための２次元のピクセル画像であって、ピクセル画像の解像度よりも微細な解像度で定義される１つ以上の形状の高解像度の２次元表示を表わしており、複数のピクセルで形成されており、各ピクセルが、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が前記形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有しているピクセル画像において、ピクセル被カバー値を設定するためのコンピュータ化された方法であって、
前記複数のピクセルのそれぞれについて、
・ピクセルの該当のサンプリング領域内を異なる方向に延びている少なくとも２つのサンプリング線のそれぞれについて、そのサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているかの関数として、線の被カバー値を割り出すこと、および
・前記２つのサンプリング線について割り出した線の被カバー値の非線形関数として、ピクセルのピクセル被カバー値を決定すること
を含んでいるコンピュータ化された方法。
【請求項２】
当該方法によって生成される２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線のうちで線の被カバー値が前記形状によってサンプリング線の２分の１が覆われた場合の値に近い方のサンプリング線の被カバー値の変化につれて、より高速に変化する請求項１に記載のコンピュータ化された方法。
【請求項３】
当該方法によって生成される２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線のうちで線の被カバー値が前記形状によってサンプリング線の２分の１が覆われた場合の値に近い方のサンプリング線の被カバー値にのみ応答して変化する請求項２に記載のコンピュータ化された方法。
【請求項４】
当該方法によって生成される２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、前記２つのサンプリング線の両方の線の被カバー値の変化に応答して変化する請求項２に記載のコンピュータ化された方法。
【請求項５】
非線形の関数が、参照テーブルにおいて少なくとも２つのサンプリング線の被カバー値の関数としてアドレス指定される位置の値を参照することによって、ピクセル被カバー値を決定する請求項１に記載のコンピュータ化された方法。
【請求項６】
参照テーブルにおいて、２つのサンプリング線の被カバー値の所与の組み合わせによってアドレス指定される位置の値が、ピクセルが線の被カバー値の該当の組み合わせを有している状況において前もってより演算集約的な方法によって計算した複数のピクセル被カバー値から導出されている請求項５に記載のコンピュータ化された方法。
【請求項７】
前記形状が、１つ以上のフォント・セット内の文字の形状であり、
当該方法が、異なるフォント・セットからの文字を描画するときに、ピクセル被カバー値を決定するために異なる参照テーブルを使用することを含んでいる請求項５に記載のコンピュータ化された方法。
【請求項８】
非線形の関数が、２つの線の被カバー値の重み付け和を含む２つのサンプリング線の被カバー値の関数としてピクセル被カバー値を決定し、前記重み付け和において、２つの線の被カバー値のそれぞれの寄与が、そのような線の被カバー値のそれぞれの中間的な線の被カバー値までの近さの程度の関数である請求項１に記載のコンピュータ化された方法。
【請求項９】
前記２つのサンプリング線が、お互いに対して直角である請求項１に記載のコンピュータ化された方法。
【請求項１０】
・前記ピクセル画像が、行および列に配置されたピクセルで構成され、
・前記被カバー値が、各ピクセルのわずか２つのサンプリング線について割り出され、一方のサンプリング線が実質的に各ピクセル行の中央を延びており、一方のサンプリング線が実質的に各ピクセル列の中央を延びている
請求項９に記載のコンピュータ化された方法。
【請求項１１】
・前記形状が、前記形状を前記ピクセル画像のピクセル解像度よりも高い解像度で定義しているアウトラインによって記述されており、
・前記線の被カバー値の割り出しが、そのような線の被カバーを前記形状のアウトラインと前記サンプリング線との間の交点の間の距離の関数として割り出す
請求項１に記載のコンピュータ化された方法。
【請求項１２】
人間による読み取りが可能な表示に使用するための２次元のピクセル画像を生成するためのコンピュータ化された方法であって、
ピクセル画像は、ピクセル画像の解像度よりも微細な解像度で定義される１つ以上の形状の高解像度の２次元表示を表わしており、
ピクセル画像は、複数のピクセルで形成されており、
各ピクセルが、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が前記形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有しており、
当該方法が、
・前記形状と前記高解像度の表示において第１の方向に延びている第１組の平行なサンプリング線との交点を計算すること、
・前記形状と前記高解像度の表示において前記第１の方向とは異なる第２の方向に延びている第２組の平行なサンプリング線との交点を計算すること、
・前記ピクセルのサンプリング領域の第１組の１つ以上のサンプリング線の被カバー値を、そのようなサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているのかの関数として割り出し、次いで前記ピクセルのピクセル被カバー値を、そのような線の被カバー値の関数として決定することによって、各ピクセルについてピクセル被カバー値を計算することを含んでいる第１のピクセル設定パスを実行すること、および
・第１のパスを実行した後に、前記形状と第２組のサンプリング線との間の１つ以上の前記交点が計算されているサンプリング領域を表わしているピクセルについてのみ第１のパスにおいて設定されたピクセル被カバー値を変更する第２のピクセル設定パスを実行すること
を含んでおり、
前記第２のパスが、そのような交点が計算されているピクセルのピクセル被カバー値を、
・前記ピクセルのサンプリング領域の第２組の１つ以上のサンプリング線の被カバー値を、そのようなサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているのかの関数として割り出し、
・次いでピクセルのピクセル被カバー値を、第１のパスにおいてピクセルについて計算された線の被カバー値および第２のパスにおいてピクセルについて計算された線の被カバー値の関数として決定すること
によって変更するコンピュータ化された方法。
【請求項１３】
・ピクセル画像が、順次のアドレスにてメモリに保存された一連のピクセル行で構成され、各ピクセル行が、より密な間隔の順次のアドレスにてメモリに保存された一連の前記ピクセル被カバー値を含んでおり、
・第１のパスが、そのようなピクセル行の方向に延びているサンプリング線について実行される
請求項１２に記載のコンピュータ化された方法。
【請求項１４】
前記ピクセル画像が、ピクセルの２次元アレイで構成されており、前記第１および第２の方向が、該アレイの２つの次元に一致している請求項１２に記載のコンピュータ化された方法。
【請求項１５】
前記第２のパスが、ピクセルについてのピクセル被カバー値を、前記第１および第２の方向に延びるサンプリング線の被カバー値の非線形関数として決定させ、ピクセル被カバー値が所与の線の被カバー値の変化の速度の関数として変化する速度が、線の被カバー値そのものの関数として変化する請求項１２に記載のコンピュータ化された方法。
【請求項１６】
人間による読み取りが可能な表示に使用するための２次元のピクセル画像を生成するためのコンピュータ化された方法であって、
ピクセル画像は、ピクセル画像の解像度よりも微細な解像度であるアウトラインによって定義される文字フォント形状の高解像度の２次元表示を表わしており、
ピクセル画像は、行および列に配置された複数のピクセルで形成されており、
各ピクセルが、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が前記形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有しており、
当該方法が、
・前記高解像度の２次元の表示において、前記形状のアウトラインと前記ピクセル行に沿って延びる平行な行サンプリング線の組との間の交点、および前記形状のアウトラインと前記ピクセル列に沿って延びる平行な列サンプリング線の組との間の交点を計算すること、
・第１のピクセル設定パスを実行すること、および
・第１のパスの実行後に、第２のピクセル設定パスを実行すること
を含んでおり、
前記計算は、
・文字フォント形状の各アウトラインを巡って前進し、そのような前進の際に生じるそのような各交点を見つけること、および
・所与のサンプリング線とのそのような各交点を、該サンプリング線に関する順序付けた交点リストにおいて、該サンプリング線の開始端までの距離を該サンプリング線において生じる他のそのような交点と比べて表わす順序付けた位置に配置すること
を含んでおり、
前記第１のピクセル設定パスは、
・各ピクセル行において、
・該当の行サンプリング線の開始端に最も近いピクセルから出発して、行の各ピクセルについて、
・行サンプリング線の関連の交点リストにピクセルのサンプリング領域において生じる交点が存在していないならば、ピクセルをサンプリング線の現在の線の被カバー状態に対応するピクセル被カバー値に設定し、
・そうでない場合に、
サンプリング線の現在の線の被カバー状態を、交点リストのピクセルのサンプリング領域の次の各交点を反映すべく変更し、
行の線の被カバー値を、ピクセルのサンプリング領域内の行サンプリング線の文字フォント形状によって覆われている部分の関数として計算し、
ピクセルを、ピクセルについて計算された行の線の被カバー値の関数として決定されるピクセル被カバー値に設定すること
を含んでおり、
前記第２のピクセル設定パスは、
・自身の関連の交点リストに交点を有している各ピクセル列において、
・該当の列サンプリング線の開始端に最も近いピクセルから出発し、該当の交点リストにおいてピクセルのサンプリング領域に交点が存在している列の各ピクセルについて、
・列サンプリング線の現在の線の被カバー状態を、交点リストのピクセルのサンプリング領域の次の各交点を反映すべく変更し、
・列の線の被カバー値を、ピクセルのサンプリング領域内の列サンプリング線の文字フォント形状によって覆われている部分の関数として計算し、
・ピクセルのピクセル被カバー値を、第１のパスにおいてピクセルについて計算された行の線の被カバー値および第２のパスにおいてピクセルについて計算された列の線の被カバー値の関数として設定すること
を含んでいる
コンピュータ化された方法。
【請求項１７】
第２のパスにおいてピクセル被カバー値をピクセルの行および列の線の被カバー値の関数として設定するために使用される関数が、非線形の関数であって、行および列の線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、ピクセルの行または列のサンプリング線のうちで線の被カバー値が前記形状によってピクセル内のサンプリング線の２分の１が覆われた場合の値に近い方のサンプリング線の被カバー値の変化につれて、より高速に変化する請求項１６に記載のコンピュータ化された方法。
【請求項１８】
人間による読み取りが可能な表示に使用するための２次元のピクセル画像についてピクセル被カバー値を設定するためのコンピュータ・プログラミングを含んでいるコンピュータで読み取ることができるメモリであって、
ピクセル画像は、ピクセル画像の解像度よりも微細な解像度で定義される１つ以上の形状の高解像度の２次元表示を表わしており、
ピクセル画像は、複数のピクセルで形成されており、
各ピクセルは、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が前記形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有しており、
前記プログラミングが、
・ピクセルの該当のサンプリング領域内を異なる方向に延びている少なくとも２つのサンプリング線のそれぞれについて、そのサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているかの関数として、線の被カバー値を割り出し、
・前記２つのサンプリング線について割り出した線の被カバー値の非線形関数として、ピクセルのピクセル被カバー値を決定する
ためのインストラクションを含んでいるコンピュータで読み取ることができるメモリ。
【請求項１９】
前記方法によって生成される２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線のうちで線の被カバー値が前記形状によってサンプリング線の２分の１が覆われた場合の値に近い方のサンプリング線の被カバー値の変化につれて、より高速に変化する請求項１８に記載のコンピュータで読み取ることができるメモリ。
【請求項２０】
人間による読み取りが可能な表示に使用するための２次元のピクセル画像についてピクセル被カバー値を設定するためのコンピュータ・システムであって、
ピクセル画像は、ピクセル画像の解像度よりも微細な解像度で定義される１つ以上の形状の高解像度の２次元表示を表わしており、
ピクセル画像は、複数のピクセルで形成されており、
各ピクセルは、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が前記形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有しており、
前記プログラミングが、
・ピクセルの該当のサンプリング領域内を異なる方向に延びている少なくとも２つのサンプリング線のそれぞれについて、そのサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているかの関数として、線の被カバー値を割り出すための演算ロジック、および
・ピクセルのピクセル被カバー値を、前記２つのサンプリング線について割り出した線の被カバー値の非線形関数として決定するための演算ロジック
のためのインストラクションを含んでいるコンピュータ・システム。
【請求項２１】
前記方法によって生成される２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線のうちで線の被カバー値が前記形状によってサンプリング線の２分の１が覆われた場合の値に近い方のサンプリング線の被カバー値の変化につれて、より高速に変化する請求項２０に記載のコンピュータ・システム。
【発明の詳細な説明】
【発明の属する分野】
【０００１】
本発明は、アンチエイリアシングを伴うアウトラインフォントおよび他のグラフィック要素のスキャン変換またはピクセル・レンダリングに関する。
【従来の技術】
【０００２】
今日では、情報の伝達に使用される画像の多くはピクセル画像であり、すなわち、個々のピクセルまたは画素のアレイで構成された画像である。コンピュータの画面上の表示は、通常は、ピクセル画像を使用して生成されている。コンピュータ用の表示装置において、ピクセルとは、完全な色値を表示するために使用することができる表示画面の最小単位を表わしている。モノクロの表示装置においては、通常はピクセルが、表示装置が点灯または消灯を行うことができる最小の面積である。カラー表示装置においては、ピクセルは、表示装置が複合色の出力を生じさせることができる画面上の最小の面積であることが多い。通常は、複合色は、赤色、緑色、および青色のサブピクセルの組など、１つのフルカラー・ピクセルを定めるために組み合わせられるサブピクセルから形成される。
【０００３】
多くの印刷画像も、やはりピクセル画像として生成される。ツートンの印刷画像においては、多くの場合、各ピクセルが、プリンタによって紙片上に形成できる最小のマークを表わす。グレースケールの印刷画像においては、多くの場合、ピクセルは、プリンタによってグレースケール画像の生成に使用される種々のグレースケール値の任意の１つを有するドット・パターンの全体が生成される最小の領域を表わす。カラーの印刷画像においては、フルカラーのピクセルが、シアン、マゼンタ、イエロー、およびブラックなどの基本色の組のそれぞれの個々のグレースケールのサブピクセルを組み合わせることによって生成される。
【０００４】
多くのビットマップ画像は、表示しようとする各ピクセルに関連付けられた色値（ここで、色値は、白または黒、グレースケール、あるいは複合色値を表わすことができる）を有するビットマップ形式で保存された情報の単なる表示である。そのようなビットマップの表示に関して必要となる演算は、ビットマップからコンピュータ・メモリのスクリーン画像の表示に使用される部位へのピクセル値の移動と大差がない。スクリーン上への表示が所与のビットマップの解像度よりも高い解像度または低い解像度である場合、ビットマップを所望のサイズへと拡大縮小すること、および得られた画像のうちで部分的にのみカバーされているピクセルの色値を、拡大縮小後のビットマップによってカバーされている程度に比例して調節することが、必要とされるすべてである。
【０００５】
他方で、コンピュータの画面または印刷出力に表示される多くのビットマップは、描画されるべき形状の記述から生み出され、そのような形状は、表示すべきビットマップ画像のピクセルのサイズよりもかなり高い解像度で記述されている。そのような場合、そのような高解像度の記述を、それらが記述している形状の適切なピクセル画像へと変換するために、或るアルゴリズムが必要になる。これは、とくには、いわゆるスケーラブル・フォントにおいて一般的である。スケーラブル・フォントは、文字のフォントであって、その形状が、直線および曲線に関して高い解像度で精密に記述されている。このため、フォントの所与の文字の形状を、単にその文字の精密な記述の所与のピクセル画像への投影を拡大または縮小することで、幅広くさまざまなサイズの範囲において表示することが可能である。
【０００６】
本明細書および後続の特許請求の範囲において、ピクセル画像の解像度よりも高いまたは微細な解像度で定められた形状とは、そのような形状の境界をピクセル画像の解像度よりも高い解像度で特定できる定義を有している形状を指す。高い解像度とは、定められた形状の解像度であり、必ずしもそのような形状を定める式または記述に使用される点または数の解像度ではない。例えば、文字の曲線または線セグメントを記述するために使用される式または記述において端点または制御点として使用されるすべての点が、所与のピクセル画像のピクセル格子の角に生じるアウトラインフォントを定めることができる。そのような場合、フォントの形状を記述するために使用される点が、ピクセル画像と同じ解像度を有することになるが、文字の形状が曲線または斜めの線を含んでいる場合、そのような線によって記述される形状の解像度は、ピクセル画像の解像度よりもはるかに高くなる。
【発明の実施の形態】
【０００７】
図１は、本発明の譲受人の名前でもある単語「Ｂｉｔｓｔｒｅａｍ」１００を示しており、文字１０２の形状が高解像度のアウトラインで記述されているため、それらの輪郭が滑らかに見えている。
【０００８】
図２は、図１の文字１０２の形状が、アウトラインの記述の解像度よりも低いピクセル解像度で表示されるときに、どのようによりギザギザに見え始めるのかを示している。
【０００９】
図３は、図２のピクセル画像の破線の囲み１０８で示された部分の拡大である。図３においては、ピクセル画像の個々のピクセル１１０が示されている。図３に示した画像のピクセルは、ビデオ表示の場合に一般的であるとおり、直交する行１１２および列１１４に配置されている。
【００１０】
図３において、大文字「Ｂ」が、３つのアウトライン１１３Ａ、１１３Ｂ、および１１３Ｃを有して示されており、小文字「ｉ」が、２つのアウトライン１１３Ｄおよび１１３Ｅを有して示されている。
【００１１】
図４は、アウトライン１１３Ａ〜１１３Ｅを、それらアウトラインによって定められる形状に対応するピクセル画像の上に重ねられた破線で示している。このピクセル画像は、図２の破線の囲み１０８内に示された「Ｂｉ」の画像に相当している。
【００１２】
図４から見て取れるように、例えばアウトライン１１３Ａ〜１１３Ｅのような高解像度のアウトラインをより低い解像度のピクセル画像へと変換するプロセスは、例えば図４に示したジグザグの縁１１８など、ジグザグの縁を有する画像を生み出すことが多い。
【００１３】
従来技術において、アンチエイリアシングとして知られるプロセスを使用することによって、ピクセル画像の縁を観察者にとってより滑らかに見えるようにできることが、よく知られている。アンチエイリアシングは、図５に示したグレースケールのピクセル１２０によって示されているように、描画されるより高解像度の形状によって部分的に覆われるピクセルに、中間の被カバー値を持たせるプロセスである。
【００１４】
図６は、個々のピクセル１１０の格子を示すことなく図５のピクセル画像を示している点を除き、図５と同一である。
【００１５】
アンチエイリアシングは、一般に、部分的に覆われるピクセルへと、当該ピクセルのうちの１つ以上の高解像度の形状によって覆われている割合に比例するカラー値またはグレースケール値としても知られる被カバー値を割り当てようとする。これが、ピクセル１１０が形状１１４によって部分的に覆われて示されている図７に表示されている。
【００１６】
図７に示したピクセル１１０について、形状によって覆われている正確な割合を計算するため、アウトラインフォントの記述によってもたらされる形状の幾何学的定義を取り上げて、幾何学的な方法を使用することが可能である。ひとたびこれが実行されると、その割合に対応する被カバー値を、アンチエイリアシングの目的のためにピクセルへと割り当てることができる。残念ながら、そのような演算はかなりの量の処理を必要とし、多数の文字をそのような正確に計算されたアンチエイリアシングにて描画することは、望ましくないほどに遅くなる可能性がある。したがって、部分的に覆われているピクセルの被カバー値を近似を使用して計算することが一般的になっている。
【００１７】
図８は、そのような近似方法の１つを示している。この方法では、描画される形状１１４のアウトラインの記述の曲線が、相応の直線セグメント１２２の連続によって近似されている。このような近似は、形状１１４の正確な面積を計算しようと試みるよりも、大幅に高速である。
【００１８】
図９は、他の従来技術の近似方法を示している。この方法は、ピクセル１１０内に位置する点１２４のアレイのそれぞれについて、その点が形状１１４の範囲に入るか否かを判断する。次いで、ピクセル内で形状１１４の範囲に入る点の、形状１１４の範囲に入らない点に対する割合の関数である被カバー値を、ピクセルへと割り当てる。
【００１９】
図１０は、本件出願の発明者によってこれまで使用されてきた近似方法を示している。この方法によれば、各ピクセルに、１〜５本の水平サンプリング線１２６および１〜５本の垂直サンプリング線１２８が組み合わせられている。各サンプリング線について、その線の何パーセントが形状１１４によって覆われているかが判断される。次いで、４つのサンプリング線のそれぞれについての被カバー値の平均に等しい被カバー値が、ピクセル１１０に割り当てられる。
【００２０】
この先の方法に使用されるプログラムは、使用の許諾を受けたＯＥＭが、水平および垂直の両方のスキャン線の数を１〜５の間の任意の値に設定できるようにしている。しかしながら、発明者は、図１０に示した両方向において３本未満のサンプリング線を使用すると、不充分な結果が生まれがちであることに気付いており、そのような被許諾者らに、各方向について少なくとも３本のサンプリング線を使用するように推奨している。
【００２１】
上述の方法はすべて、ピクセル画像における使用のために認容できるアンチエイリアシングを生み出している。図８、９、および１０に関して上述した近似は、通常は、アンチエイリアシング画像の描画の速度についてかなりの改善を生み出している。しかしながら、部分的に覆われているピクセルに対してピクセル被カバー値を割り当てるための近似方法であって、さらに高速な近似方法を生み出すことが望ましい。
【発明の概要】
【００２２】
本発明の目的は、アンチエイリアス処理されたビットマップ画像のピクセルにピクセル被カバー値をより迅速に割り当てるための装置、方法、および媒体を提供することにある。
【００２３】
本発明のさらに他の目的は、そのような装置、方法、および媒体であって、可能にする演算の軽減に鑑みて、そのようなピクセル被カバー値の割り当てがかなり正確である装置、方法、および媒体を提供することにある。
【００２４】
本発明の第１の態様によれば、人間による読み取りが可能な表示に使用するための２次元のピクセル画像において、ピクセル被カバー値を設定するためのコンピュータ化された方法が提供される。２次元のピクセル画像は、フォント化された文字またはグラフィック・デザインの形状など、ピクセル画像の解像度よりも微細な解像度で定義される１つ以上の形状の高解像度の２次元表示を表わしている。ピクセル画像は、複数のピクセルで形成されており、各ピクセルが、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が前記形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有している。
【００２５】
本発明のこの第１の態様によれば、この方法が、画像の複数のピクセルのそれぞれについて以下を含んでおり、すなわち、ピクセルの該当のサンプリング領域内を異なる方向に延びている少なくとも２つのサンプリング線のそれぞれについて、そのサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているかの関数として、線の被カバー値を割り出すこと、および前記２つのサンプリング線について割り出した線の被カバー値の非線形関数として、ピクセルのピクセル被カバー値を決定すること、を含んでいる。
【００２６】
本発明のこの第１の態様の多数の実施形態においては、当該方法によって生成される異なる方向に延びている２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線のうちで被カバー値がそのような形状によってサンプリング線の２分の１が覆われた場合の値に近い方のサンプリング線の被カバー値の変化につれて、より高速に変化する。
【００２７】
いくつかのそのような実施形態においては、２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線のうちで描こうとする形状によって２分の１が覆われた状態に近い方のサンプリング線の被カバー値にのみ応答して変化する。
【００２８】
他のそのような実施形態においては、２つのサンプリング線についての線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、２つのサンプリング線の両方の線の被カバー値の変化に応答して変化する。
【００２９】
本発明のこの第１の態様のいくつかの実施形態においては、ピクセル被カバー値の決定に使用される非線形の関数が、参照テーブルにおいて２つのサンプリング線の被カバー値の関数としてアドレス指定される位置の値を参照することによって、それらの値を決定する。線の被カバー値の所与の組み合わせについての参照テーブル内の値は、ピクセルが線の被カバー値の該当の組み合わせを有している状況において前もってより演算に関して正確かつ集約的な方法によって行われる複数のピクセル被カバー値の計算から、導出することができる。
【００３０】
描こうとする形状が、異なるフォント・セット内の文字である場合には、異なるフォント・セットからの文字を描画するときに、異なる参照テーブルを使用してピクセル被カバー値を決定することができる。
【００３１】
本発明のこの第１の態様のいくつかの実施形態においては、非線形の関数が、異なる方向に延びる２つのサンプリング線の被カバー値の重み付け和を含む関数として、ピクセル被カバー値を決定する。この重み付け和において、２つの線の被カバー値のそれぞれの寄与は、そのような線の被カバー値のそれぞれの中間的な線の被カバー値までの近さの程度の関数である。
【００３２】
本発明のこの第１の態様のいくつかの実施形態においては、異なる方向に延びる２つのサンプリング線が、お互いに対して直角である。そのようないくつかの実施形態においては、ピクセル画像が、行および列に配置されたピクセルで構成され、被カバー値が、各ピクセルのわずか２つのサンプリング線について割り出され、一方のサンプリング線が実質的に各ピクセル行の中央を延びており、一方のサンプリング線が実質的に各ピクセル列の中央を延びている。
【００３３】
本発明のこの第１の態様の多くの実施形態においては、描こうとする形状が、形状をピクセル画像のピクセル解像度よりも高い解像度で定義しているアウトラインによって記述されており、線の被カバー値が、形状のアウトラインとサンプリング線との交点の間の距離の関数として決定される。
【００３４】
本発明の第２の態様によれば、人間による読み取りが可能な表示に使用するための２次元のピクセル画像を生成するためのコンピュータ化された方法であって、２つのピクセル設定パスを使用する方法が提供される。ピクセル画像は、ピクセル画像の解像度よりも微細な解像度で定義される１つ以上の形状の高解像度の２次元表示を表わしている。ピクセル画像は、複数のピクセルで形成されており、各ピクセルが、高解像度の表示のうちの該当のサンプリング領域を表わすとともに、該当のサンプリング領域が形状のうちの１つによってどの程度覆われているかを表わすピクセル被カバー値を有している。
【００３５】
本発明のこの第２の２パスの態様は、以下を含んでいる。すなわち、前記形状と前記高解像度の表示において第１の方向に延びている第１組の平行なサンプリング線との交点を計算すること、前記形状と前記高解像度の表示において前記第１の方向とは異なる第２の方向に延びている第２組の平行なサンプリング線との交点を計算すること、ならびに第１および第２のピクセル設定パスを実行すること、を含んでいる。
【００３６】
第１のピクセル設定パスは、各ピクセルのピクセル被カバー値を、前記ピクセルのサンプリング領域の第１組の１つ以上のサンプリング線の被カバー値を、そのようなサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているのかの関数として割り出し、次いでそのような線の被カバー値の関数としてピクセルのピクセル被カバー値を決定することによって、計算することを含んでいる。
【００３７】
第２のピクセル設定パスは、第１のピクセル設定パスを実行した後に実行され、前記形状と第２組のサンプリング線との間の１つ以上の交点が計算されているサンプリング領域を呈しているピクセルについてのみ、第１のパスにおいて設定されたピクセル被カバー値を変更する。第２のパスは、そのような交点が計算されているピクセルのピクセル被カバー値を、前記ピクセルのサンプリング領域の第２組の１つ以上のサンプリング線の被カバー値を、そのようなサンプリング線がサンプリング領域内で前記形状のいずれかによってどの程度覆われているのかの関数として割り出し、次いでピクセルのピクセル被カバー値を、第１のパスにおいてピクセルについて計算された線の被カバー値および第２のパスにおいてピクセルについて計算された線の被カバー値の関数として決定することによって、変更する。
【００３８】
本発明のこの第２の２パスのいくつかの実施形態においては、ピクセル画像が、順次のアドレスにてメモリに保存された一連のピクセル行で構成され、各ピクセル行が、より密な間隔の順次のアドレスにてメモリに保存された一連のピクセル被カバー値を含んでいる。そのような実施形態においては、第１のピクセル設定パスが、そのようなピクセル行の方向に延びているサンプリング線について実行される。多くのそのような実施形態においては、ピクセル画像が、ピクセルの２次元アレイで構成されており、第１および第２の方向が、アレイの２つの次元に一致している。
【００３９】
本発明のこの２パスの態様のいくつかの実施形態においては、第２のピクセル設定パスが、ピクセルのピクセル被カバー値を、第１および第２の方向に延びるサンプリング線の被カバー値の非線形関数として決定させる。この非線形の関数においては、ピクセル被カバー値が所与の線の被カバー値の変化の速度の関数として変化する速度が、線の被カバー値そのものの関数として変化する。
【００４０】
本発明の第３の態様によれば、２次元のピクセル画像を生成するための２パスの方法であって、本発明の第２の態様の２パスの方法に類似した方法が提供される。本発明のこの第３の態様によれば、描こうとする形状が、ピクセル画像の解像度よりも微細な解像度であるアウトラインによって定義される文字フォント形状であり、画像のピクセルが、行および列に配置されている。第１組の線が、ピクセル行に沿って延びており、第２組の線が、ピクセル列に沿って延びている。この方法は、描こうとする文字フォント形状の各アウトラインを巡って前進して、このアウトラインと行および列の線との間の各交点を見つける。発見されたそのような交点のそれぞれが、交点が生じたサンプリング線に関する順序付けられた交点リストにおいて、リストにおける交点の順序にリストの関連のサンプリング線に沿った交点の順序を反映させつつ配置される。
【００４１】
本発明の第３の態様の第１のピクセル設定パスは、各ピクセル行について実行されるループを含んでいる。このループにおいては、行の各ピクセルについて、その行のサンプリング線に関するリストにピクセルのサンプリング領域内で生じる交点が存在しない場合、ピクセルがサンプリング線の現在の被カバー状態（完全に覆われているか、全く覆われていないかである）に対応するピクセル被カバー値に設定される。そうでない場合、以下のステップ、すなわち１）サンプリング線の現在の被カバー状態を、ピクセルのサンプリング領域において生じる交点リスト内の１つ以上の次の交点のそれぞれを反映すべく変更するステップ、２）行の線の被カバー値を、ピクセルのサンプリング領域内の行サンプリング線の文字フォント形状によって覆われている割合の関数として計算するステップ、および３）ピクセルを、ピクセルについて計算された行の線の被カバー値の関数として決定されるピクセル被カバー値に設定するステップ、が行われる。
【００４２】
第２のピクセル設定パスは、本発明の第３の態様においては、第１のピクセル設定パスの後で実行され、自身の関連の交点リストに交点を有している各ピクセル列について実行されるループを含んでいる。このループにおいては、列のうちで自身の交点リストにピクセルのサンプリング領域において生じる交点を有している各ピクセルについて、以下のステップ、すなわち１）列サンプリング線の現在の線の被カバー状態を、交点リストのピクセルのサンプリング領域内の次の各交点を反映すべく変更するステップ、２）列の線の被カバー値を、ピクセルのサンプリング領域内の列サンプリング線の文字フォント形状によって覆われている割合の関数として計算するステップ、および３）ピクセルのピクセル被カバー値を、第１のピクセル設定パスにおいてピクセルについて計算された行の線の被カバー値および第２のピクセル設定パスにおいてピクセルについて計算された列の線の被カバー値の関数として設定するステップ、が実行される。
【００４３】
本発明のこの第３の態様の多数の実施形態においては、第２のピクセル設定パスにおいてピクセル被カバー値を設定するために使用される関数が、非線形の関数であって、行および列の線の被カバー値の考えられる種々の組み合わせの大部分において、ピクセル被カバー値の変化の速度が、ピクセルの行または列のサンプリング線のうちで描こうとする形状によって２分の１が覆われた状態に近い方のサンプリング線の被カバー値の変化につれて、より高速に変化する。
【００４４】
本発明のさらに他の態様によれば、コンピュータ・システムおよびコンピュータで読み取ることができるメモリに保存されたコンピュータ・プログラミングであって、上述の形式の方法を実行するコンピュータ・システムおよびコンピュータ・プログラミングが提供される。
【００４５】
本発明のこれらの態様および他の態様が、好ましい実施形態についての以下の説明を添付の図面と連動させて検討することによって、さらに明らかになるであろう。
【好ましい実施形態の詳細な説明】
【００４６】
図１１は、本発明を具現化するコンピュータ・システムについて多数考えられる種類のうちの１つであるコンピュータ・システム１３０の概要を提示している。
【００４７】
システム１３０は、ランダム・アクセス・メモリ（すなわち、「ＲＡＭ」）１３６に保存されたインストラクションを実行するためのＣＰＵ１３４を有しているコンピュータ１３２を備えている。さらに、ランダム・アクセス・メモリ１３６は、ＣＰＵ１３４によって使用されるデータ値を保存している。コンピュータは、ＣＰＵとキーボード１４０およびマウス１４２などのＩ／Ｏデバイスとの間のやりとりのために設計された入力／出力（すなわち、「Ｉ／Ｏ」）インターフェイス１３８をさらに備えている。ビデオ・インターフェイス１４４が、ビデオ・モニタ１４６の画面上に画像を生成するために必要とされる電子的出力を供給する。ハードディスク・コントローラ１４８が、ＣＰＵとハードディスク１５０との間の仲立ちを行う。ハードディスク１５０は、オペレーティングシステム・プログラム１５２および１つ以上のアプリケーション・プログラム（図１１に示したアプリケーション・プログラム１５４など）など、コンピュータによって使用されるプログラムおよびデータを保存している。
【００４８】
オペレーティングシステムは、フォント化されたスケーラブル・フォントの形状など、高解像度の形状をラスタライズするためのスキャン変換コード１５６を含んでいる。システム１３０のラスタライジング・コード１５６は、従来技術の多くのアンチエイリアシング・ラスタライゼーション・コードよりも少ない演算で、したがってより高速にアンチエイリアシングのラスタライゼーションを可能にする本発明の態様を含んでいる。
【００４９】
さらに、オペレーティングシステムは、上述の一般的な形式のスケーラブル・フォントのアウトライン形状を定めたフォント１５８を保存している。
【００５０】
さらに、コンピュータ１３２は、ＣＰＵ１３４とＣＤ‐ＲＯＭドライブ１６２との間の仲立ちを行うＣＤ‐ＲＯＭコントローラ１６０を備えている。ＣＤ‐ＲＯＭドライブは、図１１に示したＣＤ‐ＲＯＭ１６４などのＣＤ‐ＲＯＭが、図１１に破線１６４Ａで示されているようにＣＤ‐ＲＯＭドライブへと挿入されたときに、そのようなＣＤ‐ＲＯＭを読み取ることができる。
【００５１】
バス１３５が、ＣＰＵ１３４をＲＡＭ１３６、Ｉ／Ｏコントローラ１３８、ビデオ・コントローラ１４４、ハードディスク・コントローラ１４８、およびＣＤ‐ＲＯＭコントローラ１６０へと接続し、これらすべてのデバイスの相互の通信を可能にしている。
【００５２】
本発明の態様を具現化するスキャン変換コード１５６を、ＣＤ‐ＲＯＭ１６４ならびに他の実質的に任意の大容量記憶装置（例えば、フロッピーディスク、リムーバブル・ハードドライブ、およびデジタル・フラッシュＲＯＭ）など、任意の種類のメモリ・デバイスに記録することができる。ひとたびそのようなプログラミング・コードがコンピュータ１３２へと入力されると、図１１に示されているように、演算システムによって使用されるハードディスクまたは他の大容量記憶装置へと従来どおりに保存される。プログラミングは、ひとたびコンピュータの大容量記憶装置に保存されると、さらに実際に使用されるときに、そのインストラクションをＣＰＵ１３４によって実行して本発明によるスキャン変換を行うことができるよう、ランダム・アクセス・メモリ１３６へとロードされる。
【００５３】
図１３〜３２は、図１３〜３２のピクセルが、３つの水平サンプリング線１２６および３つの垂直サンプリング線１２８を有するのではなく、ただ１つの水平サンプリング線１６４およびただ１つの垂直サンプリング線１６６を有する点を除き、図１０に示したピクセル１１０と同様のピクセル１１０を示している。
【００５４】
これらの図は、わずか２つのサンプリング線を使用して、図１０に関して上述したシステムにおいて行われるように、ピクセルの被カバー率をサンプリング線の被カバーの割合の平均へと設定しようとした場合に、どのようにしてかなりの不正確さが生じうるのかを説明している。
【００５５】
例えば、図１３〜１６を参照すると、水平な上縁１６８を有している形状１６６によって覆われているピクセルの一部分が、上方へと垂直方向に移動する場合、２つのサンプリング線１６４および１６６の被カバーの割合の平均が、形状の上縁１６８が水平サンプリング線１６４を横切るときに大きく跳ね上がる。これは、上縁１６８が線１６４を横切る時点において、ピクセルの被カバー部分の割合がごくわずかに増加するだけで、線１６４の全体が、全くカバーされていない状態から完全にカバーされている状態へと移行するためである。図１０に関して説明したように、ピクセルの被カバー値が、線の被カバー値の平均として計算される場合、ピクセルの被カバー値は、図１４におけるほぼ４分の１から図１５における４分の３超へと跳ね上がることになり、実際のピクセルの被カバー率がわずかなパーセントしか変化していないにもかかわらず、ほぼ５０％にもなる変化である。
【００５６】
この不正確さは、ピクセル当たりに２つのサンプリング線しか存在しないときに人間の目にとって滑らかに見える縁を生成するという仕事について、アンチエイリアシングが比較的乏しい仕事しかしないという結果を引き起こすことになる。
【００５７】
図１７〜２０は、ピクセルを横切って水平方向に移動する垂直縁１７２を有する形状１７０を示している点を除き、図１３〜１６と同様である。
【００５８】
図１８および１９は、垂直縁１７２が図１８および１９に示した位置の間を比較的わずかに動くだけで、どのようにして水平および垂直のサンプリング線１６４および１６６の被カバー率の平均に大きな跳ね上がりが生じうるのかを示している。
【００５９】
この問題に対する解決策を考え出す試みにおいて、本発明の発明者は、ピクセルの被カバー値を、水平および垂直のサンプリング線１６４および１６６の被カバー値の非線形関数として計算することで、被カバー値のより正確な見積もりを生成できることを発見した。それは、ピクセル被カバー値を２つのサンプリング値の線形関数（例えば、それらの値の平均）として計算した場合にピクセルの被カバー率のわずかな変化によって引き起こされる上述のピクセル被カバー値の大きな不連続を、排除できるからである。これは、個々のピクセルに比べて比較的大きい造作を有する形状をレンダリングするときに生じる部分的なピクセルの覆いの種類の大部分において、種々の方向に伸びているサンプリング線のうちでより中間的な被カバー値を有しているサンプリング線が、通常は、別の方向に伸びてより極端な被カバー値を有しているサンプリング線よりも、ピクセル全体の被カバー値により近い被カバー値を有するためである。非線形関数によれば、種々の線の被カバー値の寄与を、それらの線の被カバー値そのものの関数として変化させることができる。
【００６０】
図１２は、図１１に示したスキャン変換コード１５６内のアルゴリズム１９０の高度に概略化した擬似コードの記述である。このアルゴリズムは、所与のピクセルの被カバー値を、所与のピクセル内を種々の方向に延びているサンプリング線の非線形関数として計算する。このアルゴリズムは、描画すべき画像内の部分的に覆われたピクセルのそれぞれについて、ステップ１９２〜１９６の実行を生じさせる。
【００６１】
ステップ１９２は、所与の境界ピクセルにおいて第１の方向（水平方向など）に延びている１つ以上のサンプリング線について、被カバーの程度を計算する。次いで、ステップ１９４が、ピクセルにおいて第２の方向（垂直方向など）に延びている１つ以上のサンプリング線について、被カバーの程度を計算する。次いで、ステップ１９６が、ピクセルの被カバー値、またはグレースケール値を、異なる方向に延びている線の被カバー値の非線形関数として計算する。
【００６２】
図１２に示した一般的なアルゴリズムの多数の実施形態においては、ステップ１９６において使用される非線形関数が、ピクセルへと割り当てられる被カバー値を、被カバー線のうちで最も中間的な被カバー値を有する被カバー線の被カバー値とともにより迅速に変化させる非線形関数である。
【００６３】
例えば図１３において、垂直サンプリング線１６６の被カバー値が、水平サンプリング線１６４よりも、ピクセル１１０の被カバーの割合を良好に表わしていることを見て取ることができる。この場合、サンプリング線１６６が、全く覆われていないサンプリング線１６４よりも、２分の１の被カバーを表わすことにより近い被カバー値を有している、同じことが、図１４および１５においても真である。
【００６４】
図１５においては、ピクセルが、半分が覆われるよりもわずかに進んでおり、その被カバー値は、垂直線１６６の被カバー値と同じである。水平サンプリング線１６４は、完全に覆われており、したがってその被カバー値は、全体としてのピクセルの被カバー値を正確に表わしてはいない。この場合、完全に覆われている水平サンプリング線の被カバー値よりも、１／２が覆われている状態により近い水平線の被カバー値により大きな重みを与えることで、ピクセルの被カバーについてのより正確な評価がもたらされる。同じことが、程度は低いが図１６の場合にも真である。
【００６５】
図１３〜１６について説明したように最も中間的な線の被カバーにより大きな重みを与える理由は、図１７〜２０にも同様に当てはまるが、これらの場合においては、水平線１６４が、より中間的な被カバー値を有しており、全ピクセルの被カバー値について最良な推定をもたらす。
【００６６】
図２１〜２４は、垂直方向に延びる比較的長細い矩形の形状１７４を、ピクセル１１０に対する種々の位置に示している。
【００６７】
形状１７４は、図２１に示した位置を有するときは、２つのサンプリング線１６４および１６６のいずれも覆っていない。したがって、このピクセルについて計算される被カバー値は０になる。これは、この場合にはピクセルのほぼ４分の位置が実際には覆われているため、約２５パーセントの誤りであるが、本発明の発明者は、このような誤差が、形状がピクセルの１つの角にのみ広がって居る場合には、通常は人間の目にとって顕著には知覚されないことを発見した。
【００６８】
図２２に示した場面では、形状１７４の上部が水平線１６４をわずかに横切って広がり、この線を２分の１よりもわずかに少なく覆っている。垂直線１６６を横切って広がってはいない。この場合には、水平線のより中間的な被カバー値に対して、垂直サンプリング線のゼロのカバー値よりも多くの重みを与えることが、通常は正確である。なぜならば、形状１７４がピクセル１１０に比べて大きいと仮定すると、ピクセルの実際のカバー値が、より中間的なカバー値により近い可能性が高いためである。
【００６９】
図２３は、長細い形状１７４が、垂直線１６６の実質的にすべておよび水平線１６４のほぼ２分の１のみを覆っている状況を示している。この場合、水平線１６４のより中間的な被カバー値が、全ピクセルの被カバーについて、水平サンプリング線１６６のより極端な被カバー値よりも正確な評価をもたらす。
【００７０】
図２４は、より中間的な被カバー値が、より極端なゼロの被カバー値よりも、ピクセル全体の実際の被カバーの割合をよりよく表わす他の場面を示している。
【００７１】
図２５〜２８は、４５度の角度を有する縁１７８を持つ形状１７６を、ピクセル１１０に対する種々の位置に示している。この場合、２つのサンプリング線、すなわち水平サンプリング線１６４および垂直サンプリング線１６６の値が、通常はほぼ正確に同じ値を有することを、見て取ることができる。これが真であるとき、それらの被カバー値は等しく中間的であり、ピクセル全体の被カバー値の決定に等しく寄与すべきである。
【００７２】
図２９〜３２は、ピクセル１１０を、急峻な角度を有する縁１８２を持つ形状１８０が当該ピクセルに対して種々の位置に位置するものとして示している。
【００７３】
図２９においては、水平および垂直のサンプリング線のどちらも、形状によって少しも覆われていない。この場合、ピクセル１１０に被カバー値０が割り当てられる。この場合において、誤差が図２１よりもはるかに小さいことに注意すべきである。
【００７４】
図３０および３１においては、水平サンプリング線１６４が、最も中間的な被カバー値を有しており、ピクセルの被カバー値の決定においては、その値により大きな重みが与えられる。これは、水平線１６４の被カバー値がピクセル１１０の実際の被カバーに等しいため、適切である。
【００７５】
図３２においては、やはり水平サンプリング線１６４が、最も中間的な被カバー値を有しており、やはりピクセル全体の被カバー値の決定においては、より中間的な被カバー値を有するサンプリング線により大きな重みが与えることが適切である。
【００７６】
図３３〜４０は、図１１に示したスキャン変換コード１５６について考えられる多数の実施形態のうちの１つの高度に概略化した擬似コードの表現である。
【００７７】
図３３〜４０の擬似コードは、コンピュータ画面上に描画され、あるいは何らかの印刷媒体上に印刷される文字のビットマップ表現のピクセル被カバー値を計算するための２パスのプログラムを示している。このプログラムの最高レベルは、図３３に示したｄｒａｗＴｅｘｔルーチン２００によって表わされている。このルーチンは、文字の形状が図１〜５に関して上述した形式の高解像度のアウトラインによって記述されているテキストの１つ以上の線から、ピクセル画像を生成する。
【００７８】
図３３に示されているように、ｄｒａｗＴｅｘｔルーチン２００は、描画しようとするビットマップの各文字について実行されるループ２０２を含んでいる。図３３のｄｒａｗＴｅｘｔルーチンの２パスの手順は、ループ２０２の繰り返しのそれぞれにおいて実行される。この手順は、第１のｘパスを実行し、次いで第２のｙパスを実行する。大きくは図３３のループ２０６によって実行されるｘパスにおいて、被カバー値が、図３５のＸＬｉｎｅＰａｓｓルーチンによってビットマップ２５０の各ピクセルに割り当てられる。このピクセル被カバー値は、単純に、ピクセルを通過して延びるｘサンプリング線の被カバー値である。ｙパスにおいては、第１のパスにおいて設定された被カバー値が、ｙの交点が生じているピクセルについてのみ変更され、このようなパスでの演算を大きく減らしている。ｙの交点を有するピクセルについて、ピクセルの被カバー値が、ピクセルのｘおよびｙの両方のサンプリング線のカバー値の関数として決定される。
【００７９】
この２パス・ループ２０２は、ステップ２０４から２２２を含んでいる。
【００８０】
ステップ２０４が、ループ２０２の現在の文字について、図３４に示したｃｈａｒＳｅｔＵｐルーチン２２４を呼び出す。このｃｈａｒＳｅｔＵｐルーチンは、描画しようとする所与の文字について、プログラムの２パス手順のｘパスおよびｙパスを実行する前に必要な準備のステップを実行する。
【００８１】
ｃｈａｒＳｅｔＵｐルーチンは、文字のアウトライン１１３のそれぞれについてループ２２６を実行する。これが図４１に示されており、この図に示されている大文字「Ｂ」が、３つのアウトライン１１３Ａ、１１３Ｂ、および１１３Ｃを有している。このようなアウトラインのそれぞれについて、ループ２３０が、当該アウトラインの処理が完了するまで実行される。
【００８２】
ループ２３０は、ステップ２３２、２３４、および２３６を有している。ステップ２３２は、ループ２３０の現在のアウトラインを巡って、図４１に示されている当該アウトラインと水平または垂直の中央サンプリング線１６４または１６６のそれぞれとの間の次の交点２４１または２４３に達するまで前進する。本発明の発明者によって現在使用されている本発明の実施形態においては、ステップ２３２において、アウトラインの曲線部分は、短い直線セグメントの連続で近似されている。アウトラインと中央線との間の交点は、中央線と曲線の近似に使用されている直線との間の交点として発見される。本発明の他の実施形態においては、別の近似法を使用することが可能であり、あるいは追加の演算を行って、アウトラインの曲線と中央線との間の正確な交点を発見することができる。
【００８３】
交点２４１または２４３に達するたびに、ステップ２３４が、交点がｘまたはｙのどちらの中央線であるかを判断する。次いで、ステップ２３６が、交点の表現２４２または２４４を、交点のｘまたはｙの線のそれぞれに関連付けられたリンク・リスト内の適切な位置に配置する。これが図４１に示されており、符号Ｘ０〜Ｘ８が付されたリンク・リスト２３８が、水平な中央サンプリング線１６４に関連付けられ、符号Ｙ０〜Ｙ７が付されたリンク・リスト２４０が、垂直な中央サンプリング線１６６に関連付けられている。
【００８４】
交点の表現２４２または２４４のそれぞれは、その水平または垂直のサンプリング線のそれぞれとの交点のｘまたはｙ位置を含んでいる。また、そのような表現のそれぞれは、正またはマイナス１の値を有する交点のｅｄｇｅＶａｌｕｅを含んでいる。ワインディングカウント（ｗｉｎｄｉｎｇ  ｃｏｕｎｔ）を使用する従来技術のスキャン変換システムにおいて行われているように、各交点のエッジ値は、アウトラインとの交点が生じている方向から見たとき、アウトラインを巡る経路が右または左のどちらへと移動しているように見えるかによって決定される。
【００８５】
ここで説明される本発明の実施形態においては、所与のｘまたはｙのサンプリング線に沿ったｘおよびｙ位置が、３２ビットの精度、サンプリング線に沿ったピクセルの数を表わしている２６のビット、および所与のピクセル内のサンプリング線に沿った位置を表わしている最下位の６ビットで保存される。これらの６つのビットを、ゼロから６３まで、ピクセル内の長さの６４のグラデーションを定めるために使用することができる。被カバー値が、これら６４のグラデーションから計算され、２で乗算され、したがって被カバー値を、ゼロから１２６まで偶数によって変化するものとして見ることができる。
【００８６】
図４１を参照することによって、ひとたびループ２３０のプロセスが文字のアウトラインのそれぞれについて実行されると、その文字に関係するサンプリング線のそれぞれが、当該サンプリング線と文字のアウトラインとの間の各交点の表現を含んでいるリンク・リストであって、各リンク・リスト内の交点がサンプリング線に沿って正しい順序で位置しているリンク・リストを有することになることを、見て取ることができる。
【００８７】
図３４を参照すると、ひとたびループ３２０が文字のアウトライン１１３のそれぞれについて実行されると、ループ２２６が完了し、次いでステップ２４６および２４８が実行される。ステップ２４６は、ｘおよびｙのサンプリング線１６４および１６６が通過するピクセルのそれぞれについて、ピクセル被カバー値を保持するために充分に大きいグレースケール・ビットマップを形成する。
【００８８】
図４２が、そのようなビットマップ２５０を示している。このビットマップは、列２５４に配置された複数の個々の画素２５２で構成されている。各列２５４は、表現される文字内の所与のｘサンプリング線に関連付けられたすべてのピクセルを表わしている。ここに説明される本発明の実施形態においては、各ピクセルの被カバー値が、ゼロ〜１２６の間の数によって表わされ、各ピクセルの１バイトでの表現を可能にしている。
【００８９】
ひとたび図３４のステップ２４６が実行されると、ステップ２４８が、ビットマップのすべての要素の値をゼロに設定する。この時点で、所与の文字について、ｃｈａｒＳｅｔＵｐルーチンの動作が完了する。
【００９０】
再び図３３に目を向けると、ひとたびステップ２０４でのｃｈａｒＳｅｔＵｐの呼び出しがｄｒａｗＴｅｘｔルーチンへと戻ると、ステップ２０６が、ループ２０２によって描画される文字に関連付けられたそれぞれのｘ線すなわち水平線１６４についてループを実行する。ループ２０６は、ステップ２０８〜２１２を含んでいる。
【００９１】
ステップ２０８は、ポインタｆｉｌｌＳｔａｒｔを、現在のｘ線のリンク・リスト２３８の最初の交点の表現２４２へと向ける。例えば、ループ２０６が、図４１のＸ２と付されたリンク・リストを有するｘ線について実行される場合には、ｆｉｌｌＳｔａｒｔが、図４１に示されている交点２４２Ａへと向けられる。
【００９２】
次いで、ステップ２１０が、ポインタｆｉｌｌＥｎｄを、現在のｘ線のリンク・リストの第２の交点の表現へと向ける。これにより、ループ２０６が図４１のリンク・リストＸ２を有するｘ線について実行される場合には、ｆｉｌｌＥｎｄポインタがノード２４２Ｂへと向けられる。
【００９３】
ひとたびこれら２つのステップが実行されると、ステップ２１２が、ルーチンＸＬｉｎｅＰａｓｓ２５４を呼び出す。
【００９４】
図３５が、ＸＬｉｎｅＰａｓｓルーチンを示している。ＸＬｉｎｅＰａｓｓルーチンは、ｗｉｎｄｉｎｇＣｏｕｎｔ変数をゼロにするステップ２５６を有している。文字のラスタライジングの当業者であれば理解できるとおり、ワインディングカウントは、描画される文字に関連付けられた領域の或る部分が文字の内側または外側のどちらであるかを把握するために使用される。
【００９５】
次に、図３５においてＸＬｉｎｅＬｏｏｐと呼ばれているループ２５８が、ルーチンＸＬｉｎｅＰａｓｓが呼び出しされたｘサンプリング線についての処理が完了するまで実行される。ＸＬｉｎｅＬｏｏｐは、ステップ２６０〜３０４で構成されている。
【００９６】
ステップ２６０は、変数ｃｕｒｒｅｎｔＰｉｘｅｌ＃を、ｆｉｌｌＳｔａｒｔが関連付けられている交点が位置しているピクセルの番号に設定する。例えば、ＸＬｉｎｅＰａｓｓが、図４１において符号Ｘ２が付されたリンク・リストを有する線について呼び出された場合には、ステップ２６０が、ｃｕｒｒｅｎｔＰｉｘｅｌ＃を、図４１および４３に示されリンク・リスト２３８の第１の要素２４２Ａに対応する交点２４１Ａを有しているピクセル１１０Ａの番号に設定する。次いで、ステップ２６２が、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの交点が向けられた交点２４１のｅｄｇｅＶａｌｕｅを、ｗｉｎｄｉｎｇＣｏｕｎｔ変数へと加える。
【００９７】
ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄが、リンク・リストＸ２の交点の表現２４２Ａおよび２４２Ｂに向けられているとき、交点の表現２４２Ａは、形状の外側から形状の内側への変化をマークする交点を表わしているため、交点の表現２４２ＡのｅｄｇｅＶａｌｕｅは１である。このｅｄｇｅＶａｌｕｅを、それまではゼロであったｗｉｎｄｉｎｇＣｏｕｎｔへと加えることで、ｗｉｎｄｉｎｇＣｏｕｎｔが１に設定される。
【００９８】
交点の表現２４２Ｂは、形状の内側から形状の外側へと移行する交点を表わしているため、交点の表現２４２ＢのｅｄｇｅＶａｌｕｅはマイナス１である。このｅｄｇｅＶａｌｕｅを加えた後、ｗｉｎｄｉｎｇＣｏｕｎｔはゼロとなり、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄによって表わされる交点の間の距離が、中央線のうちで描画すべき形状によって覆われる長さである。
【００９９】
ひとたびステップ２６２が完了すると、ステップ２６４が、ワインディングカウントが０でない間、ループを実行する。上述の場合には、このループは、ｗｉｎｄｉｎｇＣｏｕｎｔがすでにゼロであるため、いかなるステップも実行しない。しかしながら、形状の外側から再び形状の外側までの移行を完了する前に、中央線が複数組の関連のプラス１およびマイナス１の交点を通過できるよう、ｗｉｎｄｉｎｇＣｏｕｎｔの計算を実行するとき、文字の形状の重なり合いの異なる部分を有することも可能である。図４１および４３に示した大文字「Ｂ」などのように単純な文字形状の場合には、そのような重なり合いの部分は存在しない。
【０１００】
重なり合っている形状を有する文字においては、ループ２６４は、現在のリンク・リストの交点に沿って進み、ステップ２６６が、ｆｉｌｌＥｎｄの交点を現在のリンク・リストの次の交点に設定し、ステップ２６８が、ｆｉｌｌＥｎｄの対応するｅｄｇｅＶａｌｕｅをｗｉｎｄｉｎｇＣｏｕｎｔがゼロに達するまでｗｉｎｄｉｎｇＣｏｕｎｔへと加える。
【０１０１】
ひとたびプログラムがステップ２７０に達すると、現在のｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの間の距離が、現在のｘ線において、描画される文字によって覆われ、そのように覆われてはいない部分によって境界付けられている連続部分を表わしている。
【０１０２】
この時点で、ステップ２７０が、ｆｉｌｌＥｎｄの位置がｃｕｒｒｅｎｔＰｉｘｅｌ＃を有するピクセルの内側であるか否かを確認すべくテストを行う。そのようである場合、ステップ２７２が、ｆｉｌｌＥｎｄおよびｆｉｌｌＳｔａｒｔの交点の間の距離を、現在のピクセル、すなわち図４２に示したビットマップ２５０中でｃｕｒｒｅｎｔＰｉｘｅｌ＃に含まれたピクセル番号を有しているピクセルへと加える。これは、このような場合においては、ｆｉｌｌＥｎｄおよびｆｉｌｌＳｔａｒｔの交点の間の距離を現在のピクセルのピクセル被カバー値へと加えるべきであるからである。
【０１０３】
ステップ２７０のテストが、ｆｉｌｌＥｎｄの交点が現在のピクセルに位置していないことを発見した場合、ｅｌｓｅ命令２７４が、ステップ２７６〜２９４の実行を生じさせる。
【０１０４】
ステップ２７６は、現在のピクセルの被カバー値に、ｆｉｌｌＳｔａｒｔの位置と現在のピクセルの右縁との間の距離を加える。これは、ステップ２７４のテストが満足されない場合に、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの位置の間の距離が２つ以上のピクセルにまたがって延びており、そのカバー距離がまたがっている個々のピクセルのそれぞれの個々のｘ線の被カバー値への寄与が必要とされるために行われる、
【０１０５】
ステップ２７６が、ｆｉｌｌＳｔａｒｔの交点と現在のピクセルの右縁との間の距離を図４２に示したビットマップ２５０の対応するビットマップ要素へと加えた後、ステップ２７８がｃｕｒｒｅｎｔＰｉｘｅｌ＃を増加させ、ＸＬｉｎｅＰａｓｓ２５４が実行されている現在のｘ線に沿った次のピクセルへと向ける。
【０１０６】
ひとたびこれがなされると、ステップ２８０が、ｆｉｌｌＥｎｄの交点がｃｕｒｒｅｎｔＰｉｘｅｌ＃よりも大きいピクセル番号を有するピクセルに位置しているか否かを確認すべくテストを行う。そのようである場合、ステップ２８２〜２９２が実行される。
【０１０７】
ステップ２８２は、現在のピクセルのアドレスが奇数であるか否かを確認すべくテストを行う。その場合、ステップ２８４および２８６が実行される。ステップ２８４は、現在のピクセルを値１２６へと設定し、現在のピクセルが完全に覆われていることを知らせる。次いで、ステップ２８６が、ｃｕｒｒｅｎｔＰｉｘｅｌ＃を１つだけ増加させる。
【０１０８】
ステップ２８２〜２８６が実行された後、現在のピクセルは、偶数番号のアドレスを有する。次いで、ステップ２９０および２９２で構成されるループ２８８が、ｃｕｒｒｅｎｔＰｉｘｅｌ＃がｆｉｌｌＥｎｄの交点が生じるピクセル番号よりも小さい間、実行される。ステップ２９０は、１２６の２つの連続する値をｃｕｒｒｅｎｔＰｉｘｅｌ＃のピクセルで始まるビットマップへと書き込むために、２バイトの書き込みインストラクションを使用する。次いで、ステップ２９２が、ｃｕｒｒｅｎｔＰｉｘｅｌ＃を２だけ増加させる。
【０１０９】
ループ２８８は、ｃｕｒｒｅｎｔＰｉｘｅｌ＃がｆｉｌｌＥｎｄの交点が生じるピクセルの番号と等しくなり、あるいはｆｉｌｌＥｎｄの交点が生じるピクセルの番号よりも１つだけ大きくなるまで続けられる。ひとたびこれがなされると、ステップ２９４が実行される。ステップ２９４は、ｆｉｌｌＥｎｄのピクセルに対応するピクセルを、ｆｉｌｌＥｎｄのピクセルの左縁とｆｉｌｌＥｎｄの交点の位置との間の距離に等しい被カバー値に設定する。
【０１１０】
ひとたびこれがなされると、ステップ２９６が、現在のｘ線のリンク・リストにおいてｆｉｌｌＥｎｄによって示される交点の後ろにさらなる交点が存在するか否かを確認すべく、テストを行う。存在する場合、ステップ２９８および３００が、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄをそれぞれ、現在のリンク・リストの次の２つの交点へと向ける。これは、プログラムを、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの新しい値によって示される交点にて出発して、ＸＬｉｎｅＬｏｏｐ２５８のさらなる繰り返しを実行するように準備させる。
【０１１１】
しかしながら、テスト２９６によって、現在のｘ線のリンク・リストに表わされている交点がもはや存在しないと判断される場合には、ステップ３０２が、ステップ３０４にＸＬｉｎｅＬｏｏｐ２５８からの離脱およびＸＬｉｎｅＰａｓｓ２５４の処理の終息を実行させる。これは、現在のｘ線のリンク・リストにそれ以上の交点が存在しない場合には、２パスのプロセスのうちのｘパスについて、リスト上のすべての交点が処理済みであり、当該ｘ線のすべての被カバー部分が図４２に示したビットマップ２５０の対応するピクセルに対して適切な寄与を済ませているために行われる。
【０１１２】
図３３に戻ると、ひとたびステップ２１２におけるＸＬｉｎｅＰａｓｓの呼び出しが戻されると、ステップ２１４が、ｄｒａｗｔｅｘｔルーチン２００において使用される２パスのプロセスのうちの第２のパスを開始させる。この第２のパスは、ループ２０２の繰り返しによって描画される文字に関して図４１に示したｙサンプリング線１６６のそれぞれについて実行されるループ２１４を含んでいる。ループ２１４は、ステップ２１６〜２２０を含んでいる。
【０１１３】
ステップ２１６が、ｆｉｌｌＳｔａｒｔポインタを、ループ２１４の実行の対象のｙ線のリンク・リスト２４０の最初の交点へと向ける。例えば、図４１のリンク・リストＹ３を有するｙ線が現在の線であるならば、ｆｉｌｌＳｔａｒｔは、図４１に示されている最初のｙ交点２４４Ａとなるように向けられる。
【０１１４】
ひとたびこれがなされると、ステップ２１８が、ｆｉｌｌＥｎｄのポインタを、ｙ線のリンク・リストの第２の交点へと向ける。上述の場合には、これは、図４１に示されているｙ交点２４４Ｂである。
【０１１５】
ひとたびｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄが、現在のｙ線のリンク・リストの最初の２つの交点を指すと、ステップ２２０が、この現在のｙ線についてＹＬｉｎｅＰａｓｓルーチン３０６を呼び出す。
【０１１６】
図３６が、ＹＬｉｎｅＰａｓｓルーチンを示している。このルーチンは、ｙサンプリング線と描画しようとする文字のアウトラインとの間に１つ以上の交点が存在している図４２のビットマップ２５０のピクセル２５２のみが変更される点で、図３５に示したＸＬｉｎｅＰａｓｓ２５４と異なっている。これは、第２のパスにおけるピクセル被カバー値のより複雑な計算を、文字の形状の縁に生じるピクセルのみに限定するため、とくには文字が比較的大きなサイズで描画される場合に演算を節約する。
【０１１７】
ＹＬｉｎｅＰａｓｓ３０６は、図３５のステップ２５６に相当するステップ婦３０８で開始する。このステップは、ｗｉｎｄｉｎｇＣｏｕｎｔ変数をゼロにする。次いで、ステップ３０９が、ピクセルについて現在計算されているｙ線の被カバー値を表わしている変数ＣＹをゼロにする。次に、ステップ３１０が、ｐｅｎｄｉｎｇＰｉｘｅｌ＃変数２８０をＮＵＬＬ値、すなわちｐｅｎｄｉｎｇＰｉｘｅｌ＃が図４２のビットマップ２５０の要素を現在は表わしていないことを示す数へと設定する。次に、ＹＬｉｎｅＬｏｏｐ３１２が、現在のｙサンプリング線のリンク・リスト上のすべての交点２４４が処理されるまで実行される。ＹＬｉｎｅＬｏｏｐは、ステップ３１４〜３６２で構成されている。
【０１１８】
ステップ３１４は、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの交点のｅｄｇｅＶａｌｕｅを、ｗｉｎｄｉｎｇＣｏｕｎｔへと加える。これは、図３５に関して上述したステップ２６２と同等である。多くの場合、ＹＬｉｎｅＬｏｏｐ３１２の最初の繰り返しにおいては、ｆｉｌｌＳｔａｒｔが、ｙ線のリンク・リストの最初の交点を指しており、ｆｉｌｌＥｎｄの交点が、このリストの第２の交点を指している。例えば、ＹＬｉｎｅＬｏｏｐ３１２へと最初に進んだときに図４１に示したリンク・リストＹ３を有しているｙ線が処理される場合には、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄが、それぞれ交点２４４Ａおよび２４４Ｂを指す。
【０１１９】
ｆｉｌｌＳｔａｒｔの交点が、ｙ線において形状によって覆われる連続部分を開始させ、ｆｉｌｌＥｎｄの交点が、この被カバー部分を終了させる場合、これら２つの交点の正およびマイナス１のｅｄｇｅＶａｌｕｅがステップ３１４においてｗｉｎｄｉｎｇＣｏｕｎｔへと加えられると、ｗｉｎｄｉｎｇＣｏｕｎｔはゼロに等しい。形状が重なり合っている部分形状で構成されている場合を除き、これが常に当てはまる。
【０１２０】
ｗｉｎｄｉｎｇＣｏｕｎｔがゼロでない場合、ステップ３１６が、ステップ３１８においてｆｉｌｌＥｎｄを現在のｙ線のリンク・リストの次の交点に向けるようにし、ステップ３２０においてこの新しい交点のｅｄｇｅＶａｌｕｅをｗｉｎｄｉｎｇＣｏｕｎｔへと加えるようにする。ステップ３１８および３２０は、ｗｉｎｄｉｎｇＣｏｕｎｔがゼロに等しくなるまで繰り返され、その時点で、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの交点の間の距離が、現在のｙ線の単離された連続的な被カバー部分を表わしている。
【０１２１】
ひとたびｗｉｎｄｉｎｇＣｏｕｎｔがゼロに等しくなると、ステップ３２２が、ｐｅｎｄｉｎｇＰｉｘｅｌ＃がビットマップ内のピクセルを現在特定しているか否かを確認するためにテストを行う。ｐｅｎｄｉｎｇＰｉｘｅｌ＃が或るピクセルを表わしており、ｆｉｌｌＳｔａｒｔの交点がこの係属中のピクセルの外側にある場合、ステップ３２４〜３３０が実行される。ステップ３２４が、係属中のピクセルのｘ線の被カバーを表わす変数ＣＸを、図３３のループ２０２の２パスの手順のｘパスにおいてすでに設定された係属中のピクセルの被カバー値またはグレースケール値へと設定する。
【０１２２】
次いで、ステップ３２６が、係属中のピクセルの被カバー値を、変数ＣＸおよびＣＹの両者の非線形関数として計算し、ここでＣＹは、ピクセル内のｙ線の被カバー率を表わしている。これは、図３７〜４０に示した式など、いくつかある種々の式のいずれかによって実行できる。図３７〜３９の式はすべて、計算されるピクセル被カバー値が、現在のピクセルにおいて５０パーセントの被カバーの表示に近い被カバー値を有している方のサンプリング線（ｘまたはｙのサンプリング線）の線の被カバー値により強く依存するようにしている。これらの式において、ピクセルおよび線の被カバー値は、すべてゼロ〜１２６の範囲にある。すなわち、これらの式に示される６３および６４という値が、ほぼ２分の１のカバー値を表わす。
【０１２３】
これらの式の内で最も単純な１つは、図３９に示した式である。この式は、ピクセルの被カバー値をそのｘまたはｙサンプリング線の被カバー値に設定する２択の式であり、それら２つの値のうちで５０％の被カバーをより近く表わしている方の値を選択される。ｘおよびｙの被カバー値が等しいピクセルについては、ピクセルの被カバー値としてＣＸが選択されるが、そのような場合にはＣＸがＣＹに等しいため、実際には、被カバー値がＣＸおよびＣＹの値に等しくなるように設定されるということである。本発明の他のいくつかの実施形態においては、図３９に示した２択の式は変形され、ＣＸおよびＣＹが中間値６３の反対側にあるが中間値６３からの距離が同じまたは実質的に同じである場合に、ピクセルの被カバー値が、２つの被カバー値のいずれかの値にではなく、中間値６３に設定される。
【０１２４】
ひとたびステップ３２６が現在のピクセルの被カバー値の計算のために非線形関数を使用すると、ステップ３２８が、計算された値を係属中のピクセルへと書き込む。
【０１２５】
ひとたびステップ３２８が実行されると、ステップ３３０が、将来の計算に備えてＣＹをゼロに設定する。次いで、ステップ３３２が、ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの交点が同じピクセル内にあるか否かを確認すべくテストを行う。そのようである場合には、ステップ３３３および３３６が実行される。ステップ３３４が、ＣＹを、ＣＹの先の値にｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの交点の間の距離を加えた値に等しく設定する。次いで、ステップ３３６が、ｐｅｎｄｉｎｇＰｉｘｅｌ＃をｆｉｌｌＥｎｄのピクセルのピクセル番号に設定する。
【０１２６】
ステップ３３２において条件に合致しない場合、ｅｌｓｅ命令３３８が、ステップ３４０〜３５２の実行を生じさせる。ステップ３４０は、変数ＣＹを、ＣＹの先の値にｆｉｌｌＳｔａｒｔの交点とｙ線がその交点が生じているピクセルの終わりに達する場所との間の距離を加えた値に等しく設定する。ステップ３４２は、ｐｅｎｄｉｎｇＰｉｘｅｌ＃をｆｉｌｌＳｔａｒｔが位置しているピクセルの番号に等しく設定する。次いで、ステップ３４４〜３４８が実行されるが、これらは上述したステップ３２４〜３２８と同一である。ステップ３４２が、ＣＸを、システムの２パスのプロセスのｘパスにおいて設定された係属中のピクセルの先のピクセル被カバー値に等しく設定する。次いで、ステップ３４６が、係属中のピクセルの被カバー値をＣＹおよびＣＸの関数として計算し、ステップ３４８が、計算された被カバー値を係属中のピクセルに書き込む。
【０１２７】
ひとたびステップ３４４〜３４８が完了すると、ステップ３５０が、ＣＹを、現在のｙ線がｆｉｌｌＥｎｄのピクセルの開始に出会う場所とｆｉｌｌＥｎｄの交点の位置との間の距離に等しく設定する。最後に、ステップ３５２がｐｅｎｄｉｎｇＰｉｘｅｌ＃をｆｉｌｌＥｎｄのピクセルの番号に設定する。
【０１２８】
図３６のＹＬｉｎｅＬｏｏｐを検討することによって、図３６のステップ３３２の条件が、ｙ線の独立した連続被カバー部分を開始および終了させている交点が同じピクセル内で生じている場合に満足されることを見て取ることができる。そのような場合が、図４３に示した交点２４３Ｃおよび２４３Ｄによって説明される。これら２つのｙ交点が生じているピクセルにおいて、ＣＹは、図４３に示した距離３８０に等しい。このピクセルにおいて他にｙ線の被カバー部分は存在しないため、ＣＹのこの値が、このピクセルについて２パスのプロセスのｘパスにおいて計算した先の被カバー値に相当する値ＣＸと連動させてピクセルの被カバー値を計算するために、後のＹＬｉｎｅＬｏｏｐ３１２の繰り返しにおいて、ステップ３２２〜３３０によって使用される。
【０１２９】
図４３に示した２つのｙ線の交点２４３Ｅおよび２４３Ｆは、図３６のｅｌｓｅステップ３３８が、ステップ３４０〜３５２の実行を生じさせる場合を説明している。この場合には、ステップ３４０が、ｆｉｌｌＳｔａｒｔ交点２４３Ｅの位置とこの交点のピクセル１１０Ｄの終わりとの間の距離３８２が、このピクセルの被カバー値を計算する目的においてＣＹとして使用されるようにする。
【０１３０】
ステップ３５０は、ｆｉｌｌＥｎｄの交点２４３Ｆが生じているピクセル１１０Ｆの被カバー値を計算するために使用されるＣＹを、図４３に示されており、ｆｉｌｌＥｎｄの交点とピクセル１１０Ｆの開始との間を延びている距離３８４に等しくさせる。
【０１３１】
ｆｉｌｌＳｔａｒｔおよびｆｉｌｌＥｎｄの交点の所与の組について、ステップ３２２〜３５２が完了すると、ステップ３５４が、現在のｙ線のリンク・リストにおいて現在のｆｉｌｌＥｎｄによって示されている交点の後ろにさらなる交点が存在するか否かを確認すべくテストを行う。存在する場合、ステップ３５６および３５８が実行される。ステップ３５６が、ｆｉｌｌＳｔａｒｔを現在のｙ線のリンク・リストの次の交点へと向け、ステップ３５８が、ｆｉｌｌＥｎｄをそのリストの次の交点へと向ける。ステップ３５４のテストによって、現在のｙ線のリンク・リストに後続の交点が存在しないと判断される場合には、ｅｌｓｅ命令３６０が、ステップ３６２にＹＬｉｎｅＬｏｏｐ３１２からの離脱を実行させる。
【０１３２】
ステップ３６０がＹＬｉｎｅＬｏｏｐからの離脱を行うとき、ステップ３６４が、現時点においてｐｅｎｄｉｎｇＰｉｘｅｌ＃が非ＮＵＬＬで或るか否か、すなわち描画される文字のビットマップのピクセルに関連付けられた数を有しているか否かを確認すべくテストを行う。ｐｅｎｄｉｎｇＰｉｘｅｌ＃がそのようなピクセルに関連付けられている場合、ステップ３６４は、ステップ３６６〜３７０の実行を生じさせる。
【０１３３】
ステップ３６６は、変数ＣＸを、係属中のピクセルの先の被カバー値またはグレースケール値へと設定する。次いで、ステップ３６８が、係属中のピクセルの新たな被カバー値を、図３７〜４０に示したような非線形関数を使用して、ＣＹおよびＣＸの両者の関数として計算する。次のステップ３７０が、計算されたピクセル被カバー値を係属中のピクセルへと書き込む。
【０１３４】
図４４〜５１が、図４１および４３に示した大文字「Ｂ」のピクセル被カバー値の計算のために図３９の２択のアルゴリズムが使用される場合について、図３３〜３６に関して上述した２パスの手順の動作を説明するうえで役に立つ。
【０１３５】
ここで説明される本発明の実施形態において、ピクセルおよび線の被カバー値はすべて、ゼロ〜１２６の間の範囲にある。したがって、図４４、４６、４８、および５０において、値１２６は、完全にカバーされていることを表わし、値ゼロは、カバーされていないことを表わしている。この実施形態において、１２６よりも小さい値は半透明を表わし、ゼロが完全な透明を表わしている。これは、文字の間隔が狭い場合に被カバー値の組み合わせが可能であるよう、隣接する文字について計算されたビットマップの縁の相互の重ね合わせを可能にしている。また、文字の画像を背景色または背景画像の上へと描くことを可能にしている。
【０１３６】
図４４は、大文字「Ｂ」について、図３３に示したループ２０２の最初のパス、すなわちｘパスによって計算されたピクセル被カバー値を示している。これらのピクセル被カバー値は、各ピクセルのｘ線の被カバー値に等しくなる。
【０１３７】
図４５は、図４４に示した数値的なビットマップ値を近似するために種々のグレースケールの濃淡を使用している。これは、ｘパスの後のビットマップに含まれている情報について、より視覚的に理解しやすい表現を提供するために行われている。
【０１３８】
図４６は、図４３に示され、ｙ線の交点を有している各ピクセルに関連付けられたｙ線の被カバー値を表わしている。２パスの手順の第２のパス、すなわちｙパスにおいては、このようなｙ交点が存在するピクセルについてのみ、ｙ線の被カバー値が計算される。これは、演算を少なくし、描画プロセスを高速にするために行われる。現在の実施形態においては、各ピクセルに示されているデータが、そのピクセルの処理の間のみ保存され、ストレージの要件を軽くしている。したがって、この図に示したデータが、何らかのデータ構造に一度に存在するわけではない。
【０１３９】
図４７は、図４６に示した数値データについて、グレースケールの濃淡を使用して図式的表示を提供している。
【０１４０】
図４８は、図４６に示したｙ線の被カバー値のうちで、より中間的な値を有しているもの、すなわち図４４に示した同じピクセルのｘ線の被カバー値よりも６３に近いｙ線の被カバー値を示している。図３９に示した式によれば、これらのより中間的なｙ線の被カバー値のみが、描画される文字のピクセルの被カバー値としてビットマップに書き込まれる。
【０１４１】
図４９は、この数値データの図式的表現である。
【０１４２】
図５０は、２パス・プロセスの完了時の、図４８に示したより中間的なｙ線の被カバー値が書き込まれた後の図４４のビットマップを示している。
【０１４３】
図５１は、図５０に示した数値データの図式的表示であり、２パス・プロセスの完了時の大文字「Ｂ」のアンチエイリアス済みのビットマップを示している。
【０１４４】
図５２は、考えられるｘおよびｙの被カバー値ＣＸおよびＣＹの範囲に鑑み、所与のピクセルについて図３９に示した２択の式に従って計算されるピクセル被カバー値を表わしている表である。
【０１４５】
この表においては、ｘ線の被カバー値ＣＸが、表の上部を横切って挙げられており、ｙ線の被カバー値ＣＹが、表の左側を下方へと延びる列に挙げられている。この表においては、被カバー値の一部のみが使用されている。本発明の現在の実施形態においては、ｘ線、ｙ線、およびピクセルの被カバー値が、０〜１２６の間の偶数に限定されているが、中間的な被カバー値を表示するという目的のため、６３という被カバー値がこの表に示されている。当然ながら、他の実施形態においては、他の数字付けの仕組みも使用可能である。
【０１４６】
図５３は、そのエントリ値がスプレッド・シートを使用することによって図５２の表から導出された表である。図５３の表は、図５２の表と同じ行および列の定義を有しているが、図５３の表のエントリは、２つの部分比の間の全体の比を表わしている。全体の比の分子である２つの部分比のうちの第１は、ピクセルの被カバー値の変化の速度δＡ（ここで、「Ａ」はカバーされている面積を表わしている）を、ｘ線の被カバー値の変化の速度δＣＸで除算したものである。全体の比の分母である第２の部分比は、ピクセルの被カバー値の変化の速度δＡを、ｙ線の被カバー値の変化の速度δＣＹで除算したものである。
【０１４７】
この表から見て取ることができるように、その領域の大部分において、ピクセルの被カバー値は、サンプリング線の被カバー値のうちで最も中間的な値を有しており、すなわち表においてＣＸおよびＣＹの値がどちらも６３であるエントリにより近いサンプリング線の被カバー値（ｘまたはｙ線の被カバー値）の変化とともに、より迅速に変化する。表の符号６０２が付された部分では、ｙ線の値ＣＹが、ｘ線の値ＣＸよりもより中間的な値を有している。表のこの領域においては、図３９の２択の式によれば、ＣＸ（この領域においては、ＣＹよりも極端である）が変化しても被カバー値Ａが全く変化しないため、全体の比は０である。したがって、全体の比の分子がゼロである。
【０１４８】
同様に、図５３に示した領域６０４においては、表の計算に使用したスプレッド・シートが生成する「＃ＤＩＶ０！」というエラー・メッセージによって示されているように、全体の比が無限大の値を有する。これは、この領域においてはＣＸがＣＹよりも中間的であるがゆえ、この領域においてはＣＹの値が変化してもピクセルの被カバー値Ａが全く変化しないため、この領域６０４においては全体の比の分母がゼロであるためである。
【０１４９】
図５３と同様の表が、図３７および３８に示した式について形成されるならば、それらも、それらの関連の表の領域の大部分を覆う領域であって、ピクセルの被カバー値がより中間的な値を有する線の被カバー値ＣＸまたはＣＹに関連してより迅速に変化する領域６０２および６０４とおおむね同様の形状を有する領域を有するであろう。同じことが、図４０の方法によって使用される参照テーブルによって決定されるピクセル被カバー値の変化の速度について計算される同様の表についてもおおむね真である。
【０１５０】
図５４〜５８は、本発明において使用することができるサンプリング線の他の多数の配置のうちのいくつかを示している。
【０１５１】
図５４においては、ピクセルに、２つの水平なｘサンプリング線ｘ１およびｘ２、ならびに２つの垂直なｙサンプリング線ｙ１およびｙ２が組み合わせられている。この配置においては、サンプリング線が、各ピクセルの境界において生じている。
【０１５２】
図５５では、ピクセルが、２つの水平なｘサンプリング線ｘ１およびｘ２、ならびに２つの垂直なｙサンプリング線ｙ１およびｙ２を有している。しかしながら、この場合には、サンプリング線が、それぞれ水平および垂直方向にピクセルを横切る途中のほぼ１／４および３／４の位置に生じている。
【０１５３】
図５６においては、図１３〜３２に関して検討したｘおよびｙのサンプリング線と同様に、ピクセル当たり２つのサンプリング線しか存在していないが、図５６においては、それぞれのサンプリング線がピクセルの境界に対して４５度回転させられている。結果として、＋４５と印されている１つのサンプリング線が、プラス１の傾斜を有しており、−４５と印されている１つのサンプリング線が、マイナス１の傾斜を有している。
【０１５４】
図５７においては、ピクセルが４つのサンプリング線を有しており、そのうちの＋４５Ａおよび＋４５Ｂと印されている２つが、プラス１の傾斜を有しており、−４５Ａおよび−４５Ｂと印されている２つが、マイナス１の傾斜を有している。
【０１５５】
最後に、図５８は、各ピクセルが４つのサンプリング線を有している本発明の実施形態を示している。すなわち、ｘと印されている水平な中央ｘ線、ｙと印されている垂直な中央ｙ線、ならびに１つが＋４５と印されて＋１の傾斜を有しており、１つが−４５と印されて−１の傾斜を有している２つの中央線である。この４つの中央線からなる組み合わせは、図１３〜３２に示したようにただ１つの中央のｘおよびｙ線を使用するよりも、より正確なピクセルの被カバー情報をもたらすと考えられる。しかしながら、本発明の発明者は、図１３〜３２のようにただ１つの水平な中央線およびただ１つの垂直な中央線を使用することで、通常は充分に良好な結果がもたらされ、そのようにわずか２つの線を使用することで、演算が大幅に少なくなることを確認済みである。
【０１５６】
図５９は、図５４〜５８に示したサンプリング線の配置のすべてにおいて使用することができる式３８と同様の式を示している。この式においては、２つまたは４つのサンプリング線のそれぞれに、式中の番号Ｌ１〜Ｌ４が与えられる。そのような線のそれぞれについて計算される被カバー値は、それぞれＣＬ１〜ＣＬ４と称される。サンプリング線が２本しか存在しない場合には、Ｌ３およびＬ４に関する項は削除される。図１３〜３２に示したピクセルの場合には、ひとたびＬ３およびＬ４に関する項が削除されると、図５９の式は図３８の式に一致する。
【０１５７】
図３７に示した式など、ピクセルの被カバー値をピクセルの種々のサンプリング線の被カバー値の非線形関数として計算するための他の式も、図５４〜５８に示した形式のサンプリング線を有するピクセルを取り扱うように調整できることを、当業者であれば理解できるであろう。
【０１５８】
図４０は、参照テーブルからピクセルの被カバー値を決定するための手順６５０を説明している。この手順は、ＣＸおよびＣＹの組み合わせから参照アドレスを形成するステップ６５２を含んでいる。次いで、ステップ６５４が、その参照アドレスを使用して参照テーブルから該当するピクセル被カバー値を読み出す。
【０１５９】
そのような表を保存するために必要とされるメモリを少なくするため、ＣＸおよびＣＹについて考えられるすべての値の範囲、すなわち０〜１２６の値を、それぞれが０〜７の範囲にわたる３ビットの２進数によって表わされる８つの実質的に等間隔の領域へと写像することができる。表中の各エントリのアドレスを、２つのそのような３ビット数（１つがＣＸの値についてであって、１つがＣＹの値についてである）の連続として表わすことができる。
【０１６０】
他の実施形態においては、他のサイズの参照テーブルおよび他の形式のアドレス指定の仕組みを使用することができる。例えば、図５４、５５、５７、および５８のように各ピクセルが４つのサンプリング線を有している場合には、所与のピクセル被カバー値を表わすために使用されるアドレスを、それぞれがピクセルの４つのサンプリング線の個々の１つの被カバー値を表わしている４つのそのような３ビット数から連結させることができる。
【０１６１】
図６０は、そのような参照テーブルの学習のための方法７００を示している。
【０１６２】
方法７００は、参照テーブルの学習に使用される多数の異なる文字のそれぞれのピクセル・レンダリングまたはスキャン変換のためのループ７０２の実行を含んでいる。このループ７０２において、ピクセル画像へとスキャン変換されるそれぞれの文字について、ステップ７０４が、現在の文字のビットマップの各ピクセル行についてループを実行する。ループ７０４は、ループ７０４の現在のピクセル行の各ピクセルについて実行される内側ループ７０６を含んでいる。
【０１６３】
内側ループ７０６は、ステップ７０８〜７１６を実行する。ステップ７０８は、図７または８に関して上述した方法などを使用して、現在のピクセルの被カバー値について比較的正確な計算を行う。次いで、ステップ７１０が、ピクセルが境界ピクセルであるか否か、すなわち完全な被カバーまたは非カバーを表わす被カバー値以外の被カバー値を有しているか否かを確認するため、テストを行う。
【０１６４】
現在のピクセルが境界ピクセルである場合、ステップ７１２〜７１６が実行される。ステップ７１２は、現在のピクセルについてサンプリング線の被カバー値ＣＸおよびＣＹを計算する。次いで、ステップ７１４が、ステップ７０８で計算された正確なピクセル被カバー値を、学習参照テーブルにおいて、ＣＸおよびＣＹの上記値によって表わされる数の連結によって形成されるアドレスの要素へと加える。最後に、ステップ７１６が、実行済みの学習事例の数を記録するために、ｓａｍｐｌｅＣｏｕｎｔ変数を増加させる。
【０１６５】
ひとたび学習対象のすべての文字のスキャン変換についてステップ７０２のループが実行されると、ステップ７１８が、学習テーブルの各要素をｓａｍｐｌｅＣｏｕｎｔで除算し、テーブルに保存されているピクセル被カバー値を正規化する。ひとたびこれがなされると、参照テーブルは、図４０の式によって使用できる状態である。
【０１６６】
図６１は、図５４、５５、５７、および５８に関して上述したようなピクセル当たりに３つ以上のサンプリング線を有しているスキャン変換の仕組みにおいて使用するための参照テーブルをどのように学習するのかを示している。とくに、図５９が、図５８に示した４つのサンプリング線からなる星形の配置において使用するための参照テーブルの学習のための方法７００Ａを示している。
【０１６７】
図６１の方法７００Ａは、図６０のステップ７１２および７１４の代わりに、ステップ７１２Ａおよび７１４Ａを使用する点を除き、図６０の方法７００と同一である。ステップ７１２Ａは、図６０のステップ７１２において行われるようにｘおよびｙのサンプリング線についてだけでなく、図５８に示した＋４５および−４５度の線についても、ピクセルの被カバー値を計算する。ステップ７１４Ａは、ＣＸおよびＣＹを表わす数字だけでなく、＋４５および−４５の線の被カバー値を表わす数字を含めた連結にて、学習テーブルのアドレスを指定する点で、図６０のステップ７１４と相違している。
【０１６８】
そのような学習テーブルが、事実上あらゆる種類のサンプリング線の仕組みについて容易に生成可能であることを、当業者であれば理解できるであろう。
【０１６９】
図６２および６３は、ピクセルの被カバー値を見つけるために参照テーブルを使用する他の方法であって、異なるフォント・セットのために別個の参照テーブルが使用される方法に関係している。
【０１７０】
図６３は、図６０の学習方法７００に類似する学習方法７００Ｂを示している。わずかな相違は、新たなステップ７２０および７２２の追加、ならびにステップ７１４Ｂ、７１６Ｂ、および７１８Ｂの示される変更にある。これらの相違はすべて、異なるフォント・セットのための異なる参照テーブルの学習を可能にするように設計されている。
【０１７１】
新たなステップ７２０は、方法７００Ｂの開始において実行される。ステップ７２０は、異なる参照テーブルを生成すべき異なるフォント・セットを定義する。このステップは、多くの場合、人間の選択を用いることによって実行されると考えられる。この方法の別の実施形態においては、フォント・セットを異なって定めることができる。いくつかの実施形態においては、異なるフォント・セットが、異なるフォントのサイズを代表している。他には、異なるフォント・セットが、異なるフォントの様式、または異なるフォントの様式およびサイズの組み合わせを代表している。
【０１７２】
ひとたび異なるフォント・セットが定められると、方法７００Ｂは、ステップ７１４Ｂ、７１６Ｂ、７２２、および７１８Ｂが実行されるまで、方法７００の動作と同様の様相で進行する。
【０１７３】
ステップ７１４Ｂは、現在のピクセルについて正確に計算されたピクセル被カバー値を、現在の文字のフォントが属するフォント・セットについて学習を行っている特定の参照テーブルの該当の要素へと加える点を除き、図６０のステップ７１４に類似している。
【０１７４】
ステップ７１６Ｂは、現在の文字のフォント・セットに関連付けられている別個のｓａｍｐｌｅＣｏｕｎｔ変数を増加させる点を除き、図６０のステップ７１６に類似している。
【０１７５】
ひとたびステップ７０２の学習ループのすべてが方法７００Ｂによって実行されると、ステップ７２２が、それぞれのフォント・セットについてループを実行する。そのような繰り返しのそれぞれにおいて、ステップ７１８Ｂが、そのループの該当のフォント・セットについて生成される個々の学習テーブルについて実行される。ステップ７１８Ｂは、学習テーブルのすべての要素をｓａｍｐｌｅＣｏｕｎｔで除算するという機能を、現在のフォント・セットに関連する学習テーブルについて現在のフォント・セットに関連するｓａｍｐｌｅＣｏｕｎｔにて行う点を除き、図６０のステップ７１８に類似している。
【０１７６】
図６３は、ピクセルの被カバー値を決定するために、異なるフォント・セットについて生成された別個の参照テーブルのグループを使用する点を除き、図４０の手順６５０と同様の手順６５０Ｂを示している。そのステップ６５２Ｂは、現在のピクセルのサンプリング線のカバー値を表わしている数字から、現在の参照アドレスを形成する。次いで、ステップ６５４Ｂが、描画されようとしている現在の文字のフォント・セットに関連付けられた参照テーブルにおいて、上記参照アドレスに保存されているピクセル被カバー値を取得する。
【０１７７】
本発明についての上述の説明および図面が、あくまで本発明の説明および例示のために提示されたものであり、添付の特許請求の範囲の解釈によるものを除き、本発明が上述の説明および図面に限定されるわけではないことを、理解すべきである。以上の開示を目にした当業者であれば、特許請求の範囲の技術的範囲から離れることなく、それらに変更または変形を加えることが可能である。
【０１７８】
とくには、この出願が、多くの特許出願において一般的であるよりもさらに詳しく本発明を説明しており、本発明の発明者が、本発明についてさらに詳細な教示を公衆に提示したことで、特許請求の範囲がそのようなさらに詳細な教示へと限定されてしまうことによって不等に不利益を被ることがないと確信していることに、注意すべきである。発明者が何を自身の発明であると考えているかについて正確な記載がもたらされるよう、以下の特許請求の範囲の表現には、かなりの考慮が払われており、そのような表現が、どのような細部がまさに特定の請求項に記載されている発明の一部分であると考えられ、どのような細部がまさに特定の請求項に記載されている発明の一部分であると考えられないかについて、最も正確な記載として受け取られるように希望される。
【０１７９】
コンピュータの技術分野の当業者であれば理解できるとおり、ソフトウェアにて実行されるものとして上述された機能の多くは、ハードウェアにて実行することが可能である。例えば、上述され特許請求の範囲に後述されるスキャン変換機能の多く、あるいはすべてを実行するために、ＡＳＩＣまたはマイクロプロセッサなど、専用目的のハードウェアを集積回路に配置することが可能である。
【０１８０】
同様に、コンピュータの技術分野の当業者であれば、ソフトウェアがきわめて柔軟な技術形式であって、大部分の機能が事実上無数の方法で実行可能であることを、理解できるであろう。したがって、本発明の発明者は、特許請求の範囲を、上述した特定のソフトウェアの構成、順序、および構造に限定しようとするものではない。なぜならば、当業者であれば、きわだって異なる構成、順序、および構造を有するプログラミングを使用して、特許請求の範囲の教示を容易に実行できるからである。同様に、すでに示したように、上述したもの以外の多数の種類のサンプリング線の配置ならびに多数の種類のピクセルの被カバーの計算を、本発明の多数の態様において使用することが可能である。
【０１８１】
以上の検討の大部分は、ピクセルが直交する行および列に並べられているピクセル画像の描画に集中しているが、本発明は、印刷画像の描画においてときに使用されるような非直交の行および列においても使用可能である。
【０１８２】
また、図１３および５４〜５８に示したサンプリング線の配置が、あくまで本発明において使用できると考えられるサンプリング線の考えられる多数の配置のうちのいくつかを表わしているに過ぎないことを、理解すべきである。そのような可能性のあくまで一例として、通常はアンチエイリアシングの精度を低下させてしまうと考えられるが、図５４に示したサンプリング線の配置に類似した配置であって、２つの水平なサンプリング線および２つの垂直なサンプリング線が、それらの助けによって被カバー値が計算されようとしているピクセルによって表わされる実際の領域のわずかに外側に位置している配置が可能である。そのような場合、そのようなサンプリング線は、特許請求の範囲の目的においては、そのピクセルの「サンプリング領域」内にあると考えられる。
【０１８３】
また、本発明の他の実施形態において、ピクセルの被カバー値を、ピクセルのサンプリング線の被カバー値だけでない他の情報の関数として計算することが可能であることを、理解すべきである。例えば、図６２および６３に関して上述したように、文字のフォントを、そのサイズも含め、ピクセルの被カバー値の決定のもととなる追加の情報として使用することが可能である。他の実施形態においては、隣接ピクセルの被カバー値および／またはピクセル内でのサンプリング線の被カバーの位置など、他の多数の種類の情報を使用することが可能である。
【０１８４】
さらに、ピクセル内を種々の方向に延びている線の被カバー値の関数としてピクセル値を決定するために使用される非線形関数が、シグモイド関数ならびにニューラル・ネットワークまたは他の自動学習の技法によって学習される関数など、他の種類の非線形関数であってよいことを、理解すべきである。
【０１８５】
また、本発明の特許請求の範囲が、２次元の形状の描画に限定されないことを、理解すべきである。上述した特定の方法を、３次元以上で記述されている高解像度の形状の描画を包含するように拡張できることを、当業者であれば理解できるであろう。
【０１８６】
さらに、本発明を、線または領域の所与の部分が描画しようとする形状の内側または外側のどちらであるかを把握するためにワインディングカウント以外の技法を使用するスキャン変換の仕組みにおいても使用できることを、理解すべきである。同様に、リンク・リスト以外の他のプログラミング構造も、所与のサンプリング線に関する交点の表現を保存するために使用することができる。
【０１８７】
本発明は、図１１に示したコンピュータのほかにも、多数のさまざまな形式のコンピュータにて実行可能である。いくつか挙げるならば、複数のＣＰＵを有するコンピュータや、スキャン変換プロセスの演算の実行を助けるために使用できる別途のグラフィック、ビデオ、またはＤＳＰプロセッサを備えているコンピュータにて、本発明を使用することが可能である。いわゆるネットワーク・コンピュータまたはセットトップ・コンピュータなど、ハードディスクを持たないコンピュータにおいて使用することも可能である。これらに限られるわけではないが電子ブック、パーム・コンピュータ、ウェアラブル・コンピュータ、および電子広告板など、より高解像度の形状のピクセル画像を描画するために使用される任意の形式のコンピュータにおいて使用可能である。
【図面の簡単な説明】
【０１８８】
【図１】  この場合にはアウトラインフォントによって定められるテキストの一部分の形状であるが、一連の形状の比較的高解像度の描写を示している。
【図２】  より低い解像度のピクセル画像で描いた場合の同じ形状を示している。
【図３】  図２に示したビットマップの一部の拡大であり、このビットマップの個々のピクセルを、それが描く文字のアウトラインをピクセル上に重ねつつ示している。
【図４】  文字のアウトラインが破線で示され、それらアウトラインがビットマップの実際の画像に重ねられている点を除き、図３と同様である。
【図５】  アンチエイリアス処理の後のビットマップ画像を示している点を除き、図４と同様である。
【図６】  アンチエイリアス処理後のビットマップ画像を図５に示したピクセル格子の妨げなく示している点を除き、図５と同様である。
【図７】  高解像度の形状によって部分的に覆われているビットマップの個々のピクセルを示している。
【図８〜１０】  図７のピクセルなどのピクセルについて、描こうとしている１つ以上の形状に覆われている割合の計算を高速化するために従来技術において使用されている近似方法の説明を容易にするために使用される。
【図１１】  本発明を実行できる多数の考えられるコンピュータ・システムのうちの１つを示している。
【図１２】  本発明においてピクセル画像へとピクセル被カバー値を割り当てる方法の１つについて、高度に概略化した擬似コードの記述である。
【図１３〜３２】  本発明の一態様に従ってピクセルの被カバー値を計算するために、中央の水平サンプリング線および中央の垂直サンプリング線の被カバー値をどのように使用できるのかを説明するために使用される。
【図３３〜３６】  個々の文字の形状がアウトラインフォントを使用して定められているテキストのピクセル画像をレンダリングする２パスの方法について、高度に概略化した擬似コードの記述である。
【図３７〜４０】  ピクセル画像の適切なピクセル被カバー値をピクセルの垂直および水平の両方のサンプリング線の被カバー値の非線形関数として決定するために、図３３〜３６の２パスの方法および他のピクセル設定の仕組みによって使用できる式または方法を示している。
【図４１】  文字について生成されるビットマップ画像のそれぞれの水平および垂直サンプリング線について、図３５のアルゴリズムによってどのように交点リストが用意されるのかを説明するうえで役に立つ。
【図４２】  文字について生成されたビットマップ画像をどのようにメモリに保存できるのかを説明している。
【図４３】  ピクセルのｙ線の被カバー値を図３６のアルゴリズムに従ってどのように計算できるのかを説明するうえで役に立つ。
【図４４〜５１】  図３９の２択のピクセル設定の式が使用される場合について、図３３〜３６の２パスの方法の動作を説明するうえで役に立つ。
【図５２】  種々のｘおよびｙ線の被カバー値を有するピクセルについて、図３９の式に従って計算されたピクセル被カバー値の表である。
【図５３】  図３９において使用される式の領域の大部分において、ピクセル被カバー値が、２つのサンプリング線ｘまたはｙのうちのもっとも中間的なサンプリング値を有している方の値とともにより高速に変化することを説明するために使用される表である。
【図５４〜５８】  本発明において使用することができる他の考えられる多数のサンプリング線の配置のうちのいくつかを示している。
【図５９】  図５４〜５８に示したようなサンプリング線の配置からピクセル被カバー値を計算するために使用できる多数の非線形関数のうちの１つを示している。
【図６０〜６２】  ピクセル被カバー値の決定において使用するための参照テーブルの学習のための方法を説明している。
【図６３】  図６２の方法によって学習された参照テーブルにおいて使用できるピクセル被カバー値の決定方法を説明している。
【誤訳訂正２】
【訂正対象書類名】図面
【訂正対象項目名】全図
【訂正方法】変更
【訂正の内容】
【図１】
2003506729.tif 000001
【図２】
2003506729.tif 000002
【図３】
2003506729.tif 000003
【図４】
2003506729.tif 000004
【図５】
2003506729.tif 000005
【図６】
2003506729.tif 000006
【図７】
2003506729.tif 000007
【図８】
2003506729.tif 000008
【図９】
2003506729.tif 000009
【図１０】
2003506729.tif 000010
【図１１】
2003506729.tif 000011
【図１２】
2003506729.tif 000012
【図１３】
2003506729.tif 000013
【図１４】
2003506729.tif 000014
【図１５】
2003506729.tif 000015
【図１６】
2003506729.tif 000016
【図１７】
2003506729.tif 000017
【図１８】
2003506729.tif 000018
【図１９】
2003506729.tif 000019
【図２０】
2003506729.tif 000020
【図２１】
2003506729.tif 000021
【図２２】
2003506729.tif 000022
【図２３】
2003506729.tif 000023
【図２４】
2003506729.tif 000024
【図２５】
2003506729.tif 000025
【図２６】
2003506729.tif 000026
【図２７】
2003506729.tif 000027
【図２８】
2003506729.tif 000028
【図２９】
2003506729.tif 000029
【図３０】
2003506729.tif 000030
【図３１】
2003506729.tif 000031
【図３２】
2003506729.tif 000032
【図３３】
2003506729.tif 000033
【図３４】
2003506729.tif 000034
【図３５】
2003506729.tif 000035
【図３６】
2003506729.tif 000036
【図３７】
2003506729.tif 000037
【図３８】
2003506729.tif 000038
【図３９】
2003506729.tif 000039
【図４０】
2003506729.tif 000040
【図４１】
2003506729.tif 000041
【図４２】
2003506729.tif 000042
【図４３】
2003506729.tif 000043
【図４４】
2003506729.tif 000044
【図４５】
2003506729.tif 000045
【図４６】
2003506729.tif 000046
【図４７】
2003506729.tif 000047
【図４８】
2003506729.tif 000048
【図４９】
2003506729.tif 000049
【図５０】
2003506729.tif 000050
【図５１】
2003506729.tif 000051
【図５２】
2003506729.tif 000052
【図５３】
2003506729.tif 000053
【図５４】
2003506729.tif 000054
【図５５】
2003506729.tif 000055
【図５６】
2003506729.tif 000056
【図５７】
2003506729.tif 000057
【図５８】
2003506729.tif 000058
【図５９】
2003506729.tif 000059
【図６０】
2003506729.tif 000060
【図６１】
2003506729.tif 000061
【図６２】
2003506729.tif 000062
【図６３】
2003506729.tif 000063