(57)【特許請求の範囲】
【請求項１】
プリント走査線に沿ってプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置であって、
走査線とプリントされるべきグリフの一連の輪郭との交点の値を求める手段と、
Ｎ個の遷移対を記憶するための２Ｎ個の記憶位置を含むメモリ手段と、
前記走査線に沿った新しいピクセル遷移の一連の交点値を供給する入力手段と、
前記２Ｎ個の記憶位置および前記入力手段に並列に結合されたコンパレータ手段と、
前記コンパレータ手段に結合され、新しいピクセル遷移のそれぞれの交点値に応答して、前記メモリ手段からのＮ個の同様のタイプのピクセル遷移のすべてと前記新しいピクセル遷移の順序付けを同時に行い、後で実行される塗りつぶし操作の制御に備えて、同様のタイプのすべてのピクセル遷移を前記メモリ手段に順序正しく再位置決めする制御手段と、を備え、
前記交点のそれぞれは、ピクセル値のＯＦＦからＯＮへの遷移またはＯＮからＯＦＦへの遷移を規定し、前記遷移対は、輪郭に沿ったシーケンシャルなＯＦＦからＯＮへの遷移およびＯＮからＯＦＦへの遷移から構成される、プリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【請求項２】
前記制御手段は、前記コンパレータ手段を操作して、前記２Ｎ個の記憶位置に記憶されたＯＦＦからＯＮへの交点値および前記新しいピクセル遷移のＯＦＦからＯＮへの交点値から、ＯＦＦからＯＮへの交点値の順序付けを同時に求め、前記２Ｎ個の記憶位置に記憶されたＯＮからＯＦＦへの交点値および前記新しいピクセル遷移のＯＮからＯＦＦの交点値から、ＯＮからＯＦＦへの交点値の順序付けを同時に求め、前記制御手段は、さらに、
前記ＯＦＦからＯＮへの交点値の求められた順序に応答して、前記新しいピクセル遷移の前記ＯＦＦからＯＮへの交点値および前記２Ｎ個の記憶位置に記憶された前記ＯＦＦからＯＮへの交点値を、該求められた順序でソートして前記メモリ手段に挿入する第１のスイッチ手段を有しており、
前記第１のスイッチ手段は、さらに、前記ＯＮからＯＦＦへの交点値の求められた順序に応答して、前記新しいピクセル遷移の前記ＯＮからＯＦＦへの交点値および前記２Ｎ個の記憶位置に記憶された前記ＯＮからＯＦＦの交点値を、該求められた順序でソートして前記メモリ手段に挿入する、請求項１に記載のプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【請求項３】
前記第１のスイッチ手段が、前記ＯＦＦからＯＮへの交点値および前記ＯＮからＯＦＦへの交点値を挿入した後、前記制御手段は、前記記憶されたＮ個の遷移対のそれぞれについて、最初の遷移対のＯＮからＯＦＦへの交点値が、次の遷移対のＯＦＦからＯＮへの交点値以上かどうか判断し、該最初の遷移対のＯＮからＯＦＦへの交点値が、該次の遷移対のＯＦＦからＯＮへの交点値以上ならば、該最初の遷移対のＯＦＦからＯＮへの交点値から、該次の遷移対のＯＮからＯＦＦへの交点値までの前記プリント手段による塗りつぶしを可能にする、請求項２に記載のプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【請求項４】
前記Ｎの値は、グリフに存在する可能性のある遷移対の最大数より小さく、前記装置は、該Ｎを上回る追加分の遷移対の交点値を記憶するリンクメモリ手段をさらに備えており、該リンクメモリ手段は、前記コンパレータ手段、前記制御手段および前記第１のスイッチ手段に結合され、前記追加分の遷移対の記憶を可能にする、請求項１に記載のプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【請求項５】
前記メモリ手段は、
ＯＦＦからＯＮへのピクセル遷移のＮ個の交点値を記憶するＮ個の記憶位置と、ＯＮからＯＦＦへのピクセル遷移の交点値を記憶するＮ個の記憶位置とを有しており、
前記メモリ手段は、前記ＯＦＦからＯＮへの遷移の記憶位置に記憶された値、または前記ＯＮからＯＦＦへの遷移の記憶位置に記憶された値のいずれかを、前記コンパレータ手段に同時に供給することを可能にする複数のスイッチ手段をさらに備える、請求項１に記載のプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【請求項６】
前記コンパレータ手段は、
前記複数のスイッチ手段のそれぞれに接続され、前記ＯＦＦからＯＮへのピクセル遷移の記憶された交点値、または前記ＯＮからＯＦＦへのピクセル遷移の記憶された交点値のいずれかを、前記入力手段から受け取った前記新しいピクセル遷移の交点値と比較するコンパレータを有しており、
前記コンパレータのそれぞれは、制御手段への入力を同時に供給し、該制御手段に印加される入力の順序づけを示す、請求項５に記載の装置。
【請求項７】
前記制御手段は、前記コンパレータのそれぞれの入力から該制御手段によって導き出された制御信号に応答する追加のスイッチ手段を有しており、求められた順序付けにしたがって、前記メモリ手段における交点値を再位置決めする、請求項５に記載のプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【請求項８】
Ｎが３に等しい、請求項４に記載のプリント手段のＯＮ／ＯＦＦ制御を可能にするデータを導き出す装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、グリフ（ｇｌｙｐｈ）をラスタ化ピクセルで表現するに当たって塗り潰し領域がどこに存在するかを判定する方法及び装置に関するものであり、特にラスタ塗り潰し領域の迅速な判定を可能にするため、グリフの輪郭におけるピクセル値の遷移をソーティングする改良された装置に関するものである。
【０００２】
【従来技術及びその問題点】
フォントを構成するグリフは、アウトライン・データとしてフォント・メモリに記憶されている。こうしたアウトライン・データは、グリフを構成する曲線及び直線を表した数学的関数の形で記憶される。こうしたフォント・データのラスタ化において、グリフ・アウトラインのどの部分を「塗り潰し」、どの部分を塗り潰さない、すなわち「白」のまま残すかについて判定しなければならない。
【０００３】
多くのフォントは、「非ゼロ・ワインディング法」を用いて、ラスタ化される。この方法は、イメージの外側の縁から始め、グリフの輪郭との交点を通るラスタ走査線をたどることによってラスタ化される。今後の説明においては、左から右にイメージを横切るものと仮定するが、逆方向にイメージを横切ることも可能であることが理解できるはずである。更に、グリフの輪郭をトレースする場合、「インク」はトレースされる輪郭の右に位置するものとする。交点における輪郭が正の（すなわち、上向きの）勾配を示す場合、その交点には＋１の値が割り当てられる。交点における輪郭が負の（すなわち、下向きの）勾配を示す場合、その交点には−１の値が割り当てられる。割り当てられた値が継続して合計され、この合計がゼロでない値になると、その合計がゼロでない値になった交点の右側にあたるピクセル位置を「塗り潰」さなければならないことがわかる。換言すれば、その交点から継続的な合計がゼロになる次の交点まで、全てのピクセル位置が黒または他の色の塗り潰しインクでプリントされる。
【０００４】
ラスタ走査線と輪郭の各交点は遷移点と呼ばれ、ＯＦＦからＯＮへの遷移またはＯＮからＯＦＦへの遷移のどちらかである。ＯＦＦからＯＮへの遷移は塗り潰し処理の開始位置を示す。ＯＮからＯＦＦへの遷移は塗り潰し処理の停止位置を示す。２進プリンタの場合、塗り潰し処理は、黒のピクセルで表わされ、非塗り潰し領域は、白のピクセルによって表わされる（逆の場合もある）。
【０００５】
塗り潰し領域のピクセルの位置を確認するために現在のところ用いられている方法は、判定された「遷移対」に基づくものである。ＯＮ／ＯＦＦ遷移対は、最も左に位置するＯＦＦからＯＮへの遷移の座標と、最も左に位置するＯＮからＯＦＦへの遷移の座標とを選択し、これらを対にする（ここで左から右へ走査していると仮定する）ことによって生成される。次のＯＮ／ＯＦＦ遷移対は、次に最も左に位置するＯＦＦからＯＮへの遷移の座標と、次に最も左に位置するＯＮからＯＦＦへの遷移の座標とを選択し、これらを対にすることによって生成される。このプロセスは、全遷移が対になるまで繰り返される。
【０００６】
このプロセスは、時間を浪費するし、ＯＮ及びＯＦＦ遷移の両方をＸ座標値によって、各走査線毎に、２つの独立したリストにソーティングすることが必要になる。次に、ＯＦＦ／ＯＮ遷移対リストからの最初のＯＦＦ／ＯＮ遷移対が、ＯＮ／ＯＦＦ遷移対リストからの最初のＯＮ／ＯＦＦ遷移対と対にされる。次に、オーバラップを判定して、その結果得られた遷移対リストは、適合する塗り潰し領域を形成するようにプリント処理を制御するために用いられる。
【０００７】
上述の手順を実現する際、先行技術では、グリフの輪郭を全て横切ってしまうまで、ＯＦＦからＯＮへの及びＯＮからＯＦＦへの遷移の座標を全てソーティングし、シーケンシャルな遷移リストにストアした。ソーティング処理は、新しいＸ座標をソーティング済みの座標と逐次比較する必要のある、挿入ソーティングを利用して行われる。このソーティング処理は、ラスタ化を行う関数にかなりの処理負担をかける。更に、先行技術では、遷移リストを保持するためにラスタ化関数に大量のメモリを割り当てる（最悪の場合のメモリ要求を想定して）か、あるいはかなりの計算時間を費やして計算を行い、リンク付きリストを構成する。
【０００８】
【目的】
従って、本発明の目的は、ラスタ化グリフの表現における塗り潰し領域を効率的に判定することにある。
【０００９】
本発明の別の目的は、グリフのラスタ表現における遷移対を効率的に識別し、ソーティングすることにある。
【００１０】
本発明の更に別の目的は、先行技術に比べて少ない所要メモリ量で遷移対を決定することにある。
【００１１】
【概要】
本発明の一実施例によれば、実施例の装置は走査線に沿ったプリント装置の動作中に、塗り潰し処理を可能にするためのデータを導き出す。この装置には、グリフの一連の輪郭の夫々について、走査線と輪郭の交点値を求めるプロセッサが含まれている。順番に並んでいる交点値によって、プリント装置に必要とされるＯＦＦからＯＮへの遷移及びＯＮからＯＦＦへの遷移が示される。ＯＦＦからＯＮとＯＮからＯＦＦへの順序の付いた遷移は、遷移対を構成する。この装置には、Ｎ個の遷移対を記憶するための２Ｎ個の記憶位置から構成されるメモリが含まれている。コンパレータ回路要素が２Ｎ個の記憶位置に並列に結合されている。コントローラは、コンパレータ回路要素を操作して、２Ｎ個の記憶位置中の全てのＯＦＦからＯＮへの交点値の順序と全てのＯＮからＯＦＦへの交点値の順序を決定する。スイッチ回路要素は、決定された順序のＯＦＦからＯＮへの交点値に応答して、２Ｎ個の記憶位置中でＯＦＦからＯＮへの交点値を再び順序付けし、更に決まった順序のＯＮからＯＦＦへの交点値に応答して、２Ｎ個の記憶位置中でＯＮからＯＦＦへの交点値を再び順序付ける。オーバラップ領域を判定し、オーバラップ領域が無視されるように遷移対を配列する。
【００１２】
【実施例】
図１において、プリンタの高レベルのブロック図には、コントローラ２０、プリント・エンジン２２、読出専用メモリ（ＲＯＭ）２４、及びランダム・アクセス・メモリ（ＲＡＭ）２６が含まれている。ＲＯＭ２４には、
（ｉ）プリンタがホスト・プロセッサから受信したプリント・データのページを出力するために用いるフォント・データ、及び
（ｉｉ）フォント・データを各グリフ・イメージのラスタ表現に変換するための手続２５
が納められている。ＲＡＭ２６には、ラスタ・グリフ・イメージを記憶するためのメモリ空間が含まれている。バス２８は、プリンタの各種モジュールを接続し、その間でデータ通信及び制御通信ができるようにする。非ゼロ・ワインディング法が行えるようにするため、遷移素子アレイ３０及び補助遷移素子アレイ３２が設けられており、両方ともバス２８に接続されている。
【００１３】
図２には「遷移素子」に関するブロック図が示されている。グリフと交差する各走査線毎に、少なくとも１つの遷移素子が存在する。グリフについての全遷移素子が遷移素子アレイを構成している。各遷移素子には、例えば４つの記憶領域３４、３６、３８、及び４０が含まれている。記憶領域３４、３６、及び３８は、夫々、例えば３２ビット長であり、各記憶領域には、（遷移対の）ＯＦＦからＯＮへのピクセル遷移とＯＮからＯＦＦへのピクセル遷移に関するＸ座標値が記憶されている。従って、記憶領域３４には、ＯＦＦからＯＮへの遷移に関するＸ座標値を記憶する１６ビット値と、それと対になったＯＮからＯＦＦへの遷移に関するＸ座標値を記憶するもう１つの１６ビット値が含まれる。Ｙ座標値は、所与の走査線についての遷移のＸ座標値を選択するための、遷移素子アレイへのインデクスとして用いられる。
【００１４】
ほぼ全てのラテン文字グリフは行当たり３以下の遷移対しか現れないので、図２の遷移素子には３つの遷移対記憶領域が示されている。これはいくつかのアジア文字グリフ・フォントにも当てはまる。しかし、アジア文字グリフの多くは、走査線と文字の輪郭との交点を完全に記述するには、遷移対を追加する必要がある。図２の遷移素子にはいくつかのデータ値が入っている３２ビット部分４０を含んでいるが、そのうちの１つのデータ値は遷移素子と追加分の遷移対を記憶する追加分の遷移素子を「リンク」するために用いられるデータ値である。部分４０中の第１のデータ値は、他の１つの遷移素子がグリフ内の遷移対を充分に定義するために必要であるか否かを示すリンク表示である。リンク表示が他の遷移素子の必要性を示している場合には、リンク部分領域４０には追加される遷移素子の位置のＲＡＭ内におけるアドレスも含まれている。部分４０には、「カウント」値も含まれており、第１、第２、または、第３の遷移対が現在処理中であるかどうかを明らかにする。遷移対３８、３６、３４が選択的に処理される（そして、ソーティングされる）に従い、カウント値は１から２、３へインクリメントされる。「半分」カウント値は、遷移対の最初の半分が処理済みでありまた残りの半分が処理を待っているか否かを示す。
【００１５】
グリフは順序正しく横切る必要がある（つまり、特定のポイント、すなわち「開始」点から始めて、開始点の直前のポイント、すなわち「終了」点に戻るまで、輪郭に沿って続行する）。この規則によって、対をなすＯＦＦからＯＮへの遷移及びＯＮからＯＦＦへの遷移を挿入できる。定義では、輪郭が閉曲線であるため、半分カウントがゼロであって、ＯＦＦからＯＮへの遷移が挿入されると、次の遷移はＯＮからＯＦＦへの遷移になる。また、この逆も起こる。半分カウントは対が部分的に塗り潰されていることを表示する。
【００１６】
図３を参照すると、値によって遷移対をソーティングし、また遷移対のオーバラップを判定できるようにするのに必要な回路要素に関する詳細なブロック図が示されている。遷移素子５０には、走査線（Ｙ座標値）に沿ったＯＦＦからＯＮへの遷移に関するピクセルのＸ座標値を記憶するための記憶位置５２、５４、及び５６が含まれている。同様に、記憶位置５８、６０、及び６２は、走査線に沿ったＯＮからＯＦＦへの遷移に関するピクセルのＸ座標値を記憶するようになっている。記憶位置５２、５８は第１の遷移対を構成し、記憶位置５４、６０は第２の遷移対を構成し、記憶位置５６、６２は第３の遷移対を構成する。記憶領域６４には、特定の走査線が追加の遷移素子を必要とするか否かを示すデータ及びこの遷移素子のアドレス、「カウント」値、及び「半分」値が含まれている。カウント値と半分値を組み合わせることによって、どの遷移値がソーティング中であるかが、コントローラ６６から分かるようになっている。
【００１７】
今後明らかになるように、本発明によれば、各走査線毎に、各ピクセル値遷移のＸＹ座標を識別できるようになる。次に、全ての塗り潰し領域を識別するため、遷移をソーティングすることが必要になる。Ｙ座標を利用して、遷移アレイ素子が選択され、各Ｘ座標値が、順次、「新遷移」レジスタ６８に納められる。ＯＮ／ＯＦＦ遷移ラッチ７０が、新遷移がＯＦＦからＯＮへの遷移か、あるいはＯＮからＯＦＦへの遷移かに従って、活動状態か、あるいは非活動状態かを示す。活動／非活動状態が出力ライン７２に送り出され、入力として、遷移素子５０の記憶位置からの値を受信する複数の多重スイッチ７４、７６、及び７８のスイッチング状態を制御する。更に、ライン７２における活動／非活動状態は、夫々のスイッチング状態を制御するため、３つの別の多重スイッチ８０、８２、及び８４に加えられる。（ライン７２の活動状態によって示される）ＯＦＦからＯＮへの遷移が伝えられると、多重スイッチ７４、７６、及び７８の夫々は、ＯＦＦからＯＮへの記憶位置５２、５４、及び５６の夫々に記憶されたＸ座標値を受け渡すことが可能になる。同様に、ライン７２の状態が非活動状態の場合、多重スイッチ７４、７６、及び７８は、夫々、記憶位置５８、６０、及び６２のＯＮからＯＦＦへのＸ座標値を受け渡す。ライン７２の活動状態によって、多重スイッチの夫々８０、８２、及び８４が、遷移座標値を遷移素子９２のＯＦＦからＯＮへの記憶位置８６、８８、及び９０に送る。ライン７２の状態が非活動状態の場合、多重スイッチ８０、８２、及び８４の夫々によって、遷移座標値がＯＮからＯＦＦ記憶位置９４、９６、及び９８に送り込まれる。
【００１８】
遷移素子９２には、更に、リンク、カウント、及び半分値を納める記憶部分１００が含まれている。これらの値は、回路の処理状態に基づいて更新される。理解すべきは、遷移素子９２は、独立した遷移素子の場合もあれば、あるいは遷移素子５０の場合もある（各記憶位置に先に挿入された値に、更新された値が重ね書きされる）ということである。説明を単純にするため、今後、遷移素子９２は独立した遷移素子を指すことにする。遷移素子９２の内容は、遷移アレイ３０（図１）の適正な記憶位置（インデクス＝Ｙ座標値）に戻される。
【００１９】
遷移素子９２には、特定の走査線が、それに存在する遷移対の全てを完全に表現するのに１つまたはもっと多くの「リンク」遷移素子を追加する必要のあることを表す（オーバフロー条件を検知することによって）、「ｇｏ  ｔｏ」・リンク・ラッチ１０２が関連付けられている。リンク遷移素子が記憶されているアドレスは、遷移素子９２における構成要素１００のリンク要素中にあり、この要素がＲＡＭ３２内における記憶位置を指し示す（図１も参照されたい）。
【００２０】
１本の走査線上に３つよりも多くの遷移対が存在する場合、第４の遷移対の最初の半分がソーティング・プロセス時に「オーバフロー」し、（マルチプレクサ１２０を介して）リンク・レジスタ１０４に到達する。その値は、新しい遷移レジスタ６８に渡される。同時に、「ｇｏ  ｔｏ」リンク・レジスタ１０２がセットされる。「ｇｏ  ｔｏ」リンク・レジスタ１０２をセットしたときに、記憶部分１００のリンク値がゼロである場合、新しい遷移素子をＲＡＭ３２（図１）の補助遷移素子に割り当てなければならない。記憶部分１００のリンク値がアドレスを示している場合、補助遷移素子が既に存在している。
【００２１】
補助遷移素子が存在しない場合、遷移素子５０の部分６４中のリンク、カウント、及び半分値はゼロに初期設定され、ソーティングが続行される。既存の補助遷移素子が存在する場合、それが遷移素子５０にロードされる（遷移素子９２の値はセーブされる）。次に、ソーティング処理が続行される。
【００２２】
この構成によって、大部分の遷移アレイは、３つの遷移対記憶位置とリンク／カウント／半分記憶位置だけしか含まない遷移素子から構成できるようになる。特定の走査線上に４つ以上の遷移対が存在するため、更に遷移素子を必要とする場合、追加された遷移素子はリンク・アドレスによってＲＡＭ３２の位置にリンクされる。こうして、遷移素子アレイは、大部分が１２８ビットの遷移素子から構成されるので、（全ての遷移素子が最大数の予測される遷移対を収容するのに充分な大きさを有していることを保証した先行技術に比べて）効率良くメモリを利用できる。必要があれば、ソーティング・プロセスの進行の過程で、追加される遷移素子に関して追加のメモリを割り当てることができる。
【００２３】
遷移素子アレイの構成時に、アレイの各遷移素子には、塗り潰し処理を適正に制御できるようにするため値が増すように順序付けされた遷移対が入れられる。グリフの輪郭と走査線との交点を求めるために利用される非ゼロ・ワインディング法では、必ずしも遷移対の値が増す順序に交点が配列されるとは限らない。その結果、各遷移素子（各走査線毎の）のＯＦＦからＯＮ項目とＯＮからＯＦＦ項目を、値が増すように順序付けしなければならない。
【００２４】
こうしたソーティング処理を迅速に実行するため、図３に示す回路には、夫々、多重スイッチ７４、７６、及び７８の出力に接続されたコンパレータ１０８、１１０、及び１１２が含まれている。コンパレータ１０８、１１０、及び１１２の夫々に対する別の入力は、新遷移レジスタ６８から供給される新しい遷移点のＸ座標である。コンパレータ１０８、１１０、及び１１２の夫々からの出力は、供給されたＸ座標値のどちらが大きいかを表している。コンパレータ出力は制御モジュール６６に送られ、このモジュールは、コンパレータの入力値に応答して多重スイッチ１１４、１１６、１１８、及び１２０にスイッチ制御信号を送り出す。新しい遷移のＸ座標値および多重スイッチ７４、７６、及び７８からのＸ座標値は、新遷移レジスタ６８からマルチプレクサ１１４、１１６、１１８、及び１２０の夫々に供給される。
【００２５】
多重スイッチ７４、７６、及び７８の夫々によって、記憶位置５２、５４、及び５６に見出される全てのＯＦＦからＯＮへのピクセルのＸ座標値、または、記憶位置５８、６０、及び６２において見出される全てのＯＮからＯＦＦへのピクセルに関するＸ座標値のコンパレータ１０８、１１０、及び１１２への送信が引き起こされる。マルチプレクサ７４、７６、及び７８の夫々のスイッチング状態は、ＯＮ／ＯＦＦ遷移ラッチ７０の状態によって制御される。新遷移レジスタ６８中の新しい遷移のＸアドレス値がＯＦＦからＯＮへの遷移を示す場合、ラッチ７０からの出力状態によって、前述のマルチプレクサが夫々ＯＦＦからＯＮへのピクセル遷移値を夫々が接続されたコンパレータに供給する。同様に、新しい遷移がＯＮからＯＦＦへの遷移であれば、ＯＮからＯＦＦへのピクセル遷移値が出力される。
【００２６】
コンパレータ１０８、１１０、及び１１２の夫々は、新遷移レジスタ６８中のＸ座標値と、遷移素子５０から供給されるところの記憶されていたＯＦＦからＯＮへのＸ座標値を比較する。どちらのＸ値が大きいかによって、夫々のコンパレータが制御モジュール６６にそのことを表示する。記憶位置６４からのカウント値によって、制御モジュール６６は、特定の操作サイクルの間にコンパレータ１０８、１１０、及び１１２からのどの出力を検査すべきかを判定できる。
【００２７】
（事情に応じて）コンパレータ１０８、１１０、または、１１２から１つの（または、複数の）を受信すると、制御モジュール６６は、１つまたは複数の多重スイッチ１１４、１１６、１１８、及び１２０に制御信号を与える。これらの信号によって、多重スイッチに送られる入力の１つが夫々の出力にスイッチされ、マルチプレクサ８０、８２、及び８４を介して遷移素子９２に（あるいはリンク・アドレス・モジュール１０４に）挿入するために利用可能になる。
【００２８】
遷移値の座標を遷移素子９２中で再配置するソーティング処理は２クロック・サイクルの間に並列実行されるので、３つの遷移座標を同時にソーティングすることができる。全てのソーティングが行われると、制御モジュール６６はソーティングされた遷移対にオーバラップが存在するか否かを判定し、存在すれば、いくつかの遷移座標を無視すべきものとマーキングする。次に、塗り潰しリストが各走査線毎に作成され、ページの各グリフ毎に、同様の塗り潰しリストと共に、ＲＡＭ領域１０８に挿入される。この時点において、ＲＡＭ部分１０８からの塗り潰しリストを用いて、ラスタ・バッファへの塗り潰しデータの入力が制御される。
【００２９】
次に、図４及び５を参照すると、図３の回路によって実行される遷移対ソーティング手続を説明する例が示されている。フォント・データ記憶２４（図１）から受信されたグリフ１２０は３つの輪郭トレース、すなわち輪郭トレース１、輪郭トレース２、及び輪郭トレース３を記述するデータから構成されている。各輪郭トレースに沿った移動方向は、「右のインク」の規則に基づくものである。トレース方向は左のインクに関連づけることも可能であるが、全ての輪郭を同様にトレースしなければならない。実施例では、走査線１２０と輪郭トレース１、２、及び３の夫々との間の交点Ａ〜Ｆの夫々について、Ｘ座標値の取扱いが考察される。
【００３０】
輪郭トレース１が考察すべき最初の輪郭であると仮定すると、走査線１２２と輪郭トレース１の間の第１の交点はポイントＡである。ポイントＡにおける輪郭１の勾配のため、遷移がＯＦＦからＯＮになり、従って、ＯＮ／ＯＦＦ遷移ラッチ７０（図３）が、ライン７２における活動状態を示すことがわかる。その結果、多重スイッチ７４、７６、及び７８の夫々は、記憶位置５２、５４、及び５６を夫々の出力に接続する。更に、遷移点ＡのＸ座標値は新遷移レジスタ６８に挿入される。ここでこのレジスタのＸ座標値は、入力としてコンパレータ１０８、１１０、及び１１２、及び多重スイッチ１１４、１１６、１１８、及び１２０の夫々に供給される、遷移点Ａは走査線１２２上で遭遇する最初の遷移点であると想定しているので、記憶位置５２、５４、及び５６の夫々にはデータが入っていない。
【００３１】
現在、記憶位置６４におけるリンク値はゼロであり（リンクが不要である）、遷移素子５０中に完全な遷移対が存在しないので、カウント値はゼロに等しくなり、遷移素子５０に半分塗り潰された対が存在しないので、半分値もゼロに等しくなる。すなわち、ＯＮ＃１及びＯＦＦ＃１は空である。
【００３２】
前述の状態の結果、制御モジュール６６は、コンパレータ１０８、１１０、及び１１２の出力を無視し、遷移点Ａに関するＸ座標点をマルチプレクサ１１４及び８０を介してＯＮ記憶位置８６に送り込む。次に、遷移素子９２の記憶位置１００中の各値が更新される。リンク値はゼロに等しいままであり、カウント値はゼロにとどまり（最初の遷移対が処理中のため）、次に操作すべきは第１の遷移対におけるＯＦＦ遷移メモリ位置であることを表すため、半分値が１にセットされる（すなわち、遷移対の半分が遷移対＃１に関して存在する）。図５のライン１に示すように、遷移点ＡのＸ座標値がＯＮ記憶位置８６に存在する。
【００３３】
遭遇する次の遷移点は、輪郭トレース１を継続してトレースすることによって生じるものであり、遷移点Ｂである。遷移点Ｂは、負の輪郭勾配によるＯＮからＯＦＦへの遷移であることがわかる。その結果、ＯＮ／ＯＦＦ遷移レジスタ７０は、非活動状態にセットされ、多重スイッチ７４、７６、及び７８の夫々が、ＯＦＦ記憶位置５８、６０、及び６２の夫々に接続される。同様に、マルチプレクサ８０、８２、及び８４の夫々が、ＯＦＦ記憶位置９４、９６、及び９８に接続される。遷移素子９２における記憶位置の現在の状態がメモリ（ＲＡＭ３０）にロードされ、後で、遷移素子５０にロードされる。
【００３４】
遷移点ＢのＸ座標値が、次に新遷移レジスタ６８にロードされ、入力としてコンパレータ１０８、１１０、及び１１２に供給され、更に、入力として多重スイッチ１１４、１１６、１１８、及び１２０の夫々に供給される。
【００３５】
記憶位置５８、６０、及び６２のどれにも値がないので、制御モジュール６６は、コンパレータ１０８、１１０、及び１１２の夫々からの出力を無視して、遷移点Ｂの座標値が、多重スイッチ１１４及び８０を介して、遷移素子９２のＯＦＦ記憶位置９４に送り込まれるようにする（図５のチャートの行２参照）。この時点では記憶位置８６及び９４の両方に遷移点Ａ及びＢのＸ座標値が含まれているので、カウント値は、１にスイッチされ、次に検討すべきは第２の遷移対であることを指示する。リンク及び半分値はゼロである。
【００３６】
輪郭トレース１及び走査線１２２に沿ってそれ以上の遷移点が存在しないので、輪郭トレース２をたどると見つかる次の遷移点はＣである。遷移点Ｃにおける勾配は正のため（トレース方向において）、ＯＮ／ＯＦＦ遷移ラッチ７０によって出力ライン７２が活動状態にセットされ、多重スイッチ７４、７６、及び７８の夫々がＯＮ記憶位置５２、５４、及び５６の査定を行う。同様に、多重スイッチ８０、８２、及び８４は、出力をＯＮ記憶位置８６、８８、及び９０にスイッチする。遷移素子９２の記憶位置における現在値がメモリ（ＲＡＭ３０）にロードされ、後で、遷移素子５０にロードされる。
【００３７】
次に、遷移点ＣのＸ座標が新遷移レジスタ６８にロードされ、コンパレータ１０８、１１０、及び１１２の夫々に出力される。この例では、カウント値は、１に等しくなるようにセットされるので、制御モジュール６６は、コンパレータ１０８の出力を調べて、遷移点ＣのＸ座標値が、遷移点ＡのＸ座標値を超えるＸ値を示すことを確認する。その結果、制御モジュール６６は、遷移点ＡのＸ位置値が最小であり、遷移点Ａが、ＯＮ記憶位置のポイント８６にとどまることを確認する。その結果、多重スイッチ１１４に対する制御信号によって、多重スイッチ７４の出力に生じるＸ値がライン１３０を介して多重スイッチ１１４に送られる。遷移点ＡのＸ座標値が、多重スイッチ８０を介してＯＮ記憶位置８６に送られる。
【００３８】
同様に、制御モジュール６６は、制御電位を三路多重スイッチ１１６に加え、遷移点ＣのＸ座標値がＯＮ記憶位置８８に入力されるようにする（多重スイッチ１１６の中央のアーム、多重スイッチ８２を介して）。
【００３９】
図５の行３に示すように、遷移点Ａ、Ｂ、及びＣは、今、遷移素子９２の記憶位置８６、９４、及び８８に存在する。リンク値は、ゼロのままであり、カウント値は、１にセットされたままであり、第２の遷移対がまだ処理中であることを表しており、半分値は、次に検討すべきはＯＦＦ遷移値であることを表す１にセットされている。
【００４０】
図４に戻ると、輪郭トレース２において次に見つけ出すべき遷移点は、負の勾配のため、ＯＮ／ＯＦＦ遷移ラッチ７０が非活動状態にスイッチされるポイントＤである。多重スイッチ７４、７６、及び７８をスイッチすることによって、ＯＦＦ記憶位置５８、６０、及び６２からの入力にアクセスすることが可能になる。同様に、多重スイッチ８０、８２、及び８４をスイッチすることによって、その出力がＯＦＦ記憶位置９４、９６、及び９８に接続される。遷移素子９２における座標値は、最終的には、遷移要素５０の対応する位置にロードされる。
【００４１】
次に、遷移点ＤのＸ座標値が、新遷移レジスタ６８にロードされ、コンパレータ１０８、１１０、及び１１２に送られる。カウント値はまだ１にセットされているので、制御モジュール６６は、コンパレータ１０８の出力を調べる。コンパレータ１０８に対する入力が遷移点ＢのＸ座標であり（ＯＦＦ記憶位置５８からの）、新遷移点ＤのＸ座標位置である。新遷移点ＤのＸ座標値は、遷移点ＢのＸ座標値より小さいので、コンパレータ１０８は、その関係を制御モジュール６６に指示する。これに応答し、制御モジュール６６は、新遷移点ＤのＸ／Ｙ座標値をＯＦＦ記憶位置９４にロードする多重スイッチ１１４に信号を加える（現在記憶されている交点ＢのＸ／Ｙ座標値の代わりに）。３入力多重スイッチ１６は、やはり、交点ＢのＸ／Ｙ座標値をＯＦＦ記憶位置９６にロードするように（ライン１３０、多重スイッチ１１６の最も左のアーム、及び多重スイッチ８２を介して）制御される。
【００４２】
この時点において、図５の行４に示すように、記憶位置８６、９４、８８、及び９６には、夫々、遷移点Ａ、Ｄ、Ｃ、及びＢのＸ座標値が含まれている。リンク値は、ゼロのままであり、カウント値は、第３の遷移対（記憶位置５６及び６２）を検討するので、２に更新される。半分値は、ゼロに等しくなるようにセットされており、次の遷移対が空であることを示している。
【００４３】
図４に戻ると、輪郭トレース３のトレースによって、ＯＦＦからＯＮへの遷移点Ｅ及びＯＮからＯＦＦへの遷移点Ｆが見つかる。遷移点Ｅ及びＦは、両方とも、遷移点Ｃ及びＢの間に塗り潰される領域にオーバラップするが、オーバラップ状態は、全ての遷移点のソーティングが済むまで、考慮されない。
【００４４】
遷移点ＥのＸ座標値が、新遷移レジスタ６８にロードされ、ＯＮ／ＯＦＦ遷移ラッチ７０により、出力ライン７２に活動レベルが送り出される。交点Ａ、Ｄ、Ｃ、及びＢのＸ座標値が、夫々、ＲＡＭ３０（以前にあった遷移素子９２中）から記憶位置５２、５８、５４、及び６０にロードされる。ライン７２の活動レベルによって、遷移点Ａ及びＣのＸ座標値が夫々、コンパレータ１０８及び１１０に送られる。コンパレータ１０８では、遷移点ＥのＸ座標値が、遷移点ＡのＸ座標値よりも大きいと判定される。コンパレータ１１０では、遷移点ＥのＸ座標値が、遷移点ＣのＸ座標値より大きいことがわかる。こうした判定によって、制御モジュール６６は、多重スイッチ１１４及び１１６の右側のアームに付勢する。遷移点ＡのＸ座標値は、従って、（ライン１３０を介して）記憶位置８６に入力され、遷移点ＣのＸ座標値は、記憶位置８８に入力される。
【００４５】
制御モジュール６６は、マルチプレクサ１１８に対する制御電位の印加も行い、その中央のアームによって、遷移点ＥのＸ座標値が記憶位置９０に送り込まれる。その結果、記憶位置８６、９４、８８、９６、及び９０には、この時点において、夫々、遷移点Ａ、Ｄ、Ｃ、Ｂ、及びＥが含まれている。隔サイクル毎、ＯＦＦからＯＮへの全遷移またはＯＮからＯＦＦへの全遷移が、ソーティングされる。
【００４６】
遷移点Ｆを検討する際に、同様の操作が行われるが、想起されるように、遷移点Ｆは、ＯＮからＯＦＦへの遷移であり、全てのＯＮからＯＦＦへの記憶位置が使用可能になる。ソーティング処理の前に、Ａ、Ｄ、Ｃ、Ｂ、及びＥの値が、遷移素子５０にロードされる。遷移素子５０の状態が、図５の行５に示されている。次に、新遷移点ＦのＸ座標値が、新遷移レジスタ６８にロードされる。記憶位置６４のリンク値は、ゼロのままであり、カウント値は、２にセットされ、半分値は、ＯＦＦ遷移のソーティング中であることを表す、１にセットされている。非活動状態が、ＯＮ／ＯＦＦ遷移ラッチ７０からの出力ライン７２に生じる。
【００４７】
こうした環境において、新遷移点Ｆ及び遷移点ＤのＸ座標値が、コンパレータ１０８において比較され、遷移値ＦのＸ座標値のほうが大きいと判定される。同様に、遷移点ＦのＸ座標値と遷移点ＢのＸ座標値が比較され、遷移点ＢのＸ座標値のほうが大きいということがわかる。その結果、制御モジュール６６は、コンパレータ１０８及び１１０からの入力に応答して、多重スイッチ１１４、１１６、及び１１８に制御信号を与える。
【００４８】
今や明らかなように、ＯＮからＯＦＦへの遷移に関するＸ座標値は、遷移点Ｄ、Ｆ、及びＢに関するＸ座標値の増大を示している。従って、多重スイッチ１１４、１１６、及び１１８は、次のように制御される：多重スイッチ１１４が、右側の脚を介して、記憶位置５８から記憶位置９４（遷移素子９２における）に遷移点ＤのＸ座標値を送り、多重スイッチ１１６が、中央の脚を介して、記憶位置９６に遷移点ＦのＸ座標値を送り、多重スイッチ１１８が、左側の脚を介して、記憶位置９８に遷移点ＢのＸ座標値を送る。遷移素子９２における記憶位置の最終状態は、図５のチャートの行６に示すとおりである。
【００４９】
上記では明示的に考察していないが、理解しておくべきは、遷移素子５０から遷移素子９２へのＯＦＦからＯＮへの値の更新及びソーティング中、ＯＮからＯＦＦへの値は、全て、不変のままという点である。同様に、ＯＮからＯＦＦへの値のソーティング中、ＯＦＦからＯＮへの値は不変のままである。
【００５０】
行６の検討から明らかなように、ＯＦＦからＯＮへの遷移Ａ、Ｃ、及びＥは、増大するＸ座標値に基づいてソーティングされた。同様に、ＯＮからＯＦＦへの遷移Ｄ、Ｆ、及びＢも、増大するＸ座標値に基づいてソーティングされた。しかし、図４の例に示されるように、ＯＮ／ＯＦＦ遷移対Ｃ及びＦにＯＮ／ＯＦＦ遷移対Ｅ及びＢがオーバラップしているので、ソーティング手順は、まだ終了していない。
【００５１】
以上の解説全般を通じて、「右のインク」フォント・フォーマットについて考察してきた。グリフが「左のインク」となる場合も起こる可能性がある。こうした事態を取り扱うため、ソーティング済みの各遷移対は、遷移素子５０に再挿入することが可能である。各遷移対を比較することによって、そのＯＦＦからＯＮへのＸ座標値が、ＯＮからＯＦＦへのＸ座標値より小さいことが確認される。そうでなければ、その値は、逆にされる。コンパレータ１０８、１１０、及び１１２を利用して、一度に、３つの遷移対について、この処理を同時に実施することが可能である。
【００５２】
オーバラップを補正するため、遷移素子９２の各ＯＦＦのＸ座標値が、制御モジュール６６によって、直後のＯＮ遷移のＸ座標値と比較される。直後のＯＮ遷移のＸ座標値が、直前のＯＦＦ遷移のＸ座標値に等しいか、あるいはそれより小さい場合、オーバラップを生じることが分かっている。こうした場合には、最初の遷移対のＯＮからＯＦＦへの遷移と、直後の遷移対のＯＦＦからＯＮへの遷移が、両方とも、無視され、塗り潰し処理が、最初の遷移対のＯＮ遷移から後続の遷移対のＯＦＦ遷移へと進行する。図４の場合、この手順によって、塗り潰し操作時に、ＯＮ遷移Ｅ及びＯＦＦ遷移Ｆの両方を無視することが可能になる、従って、ＯＦＦからＯＮへの遷移Ｃ〜ＯＮからＯＦＦへの遷移Ｂの間において塗り潰しが可能になる。
【００５３】
上述の操作の結果、ソーティング機能を実施するための最小限の操作サイクルを利用して、塗り潰しリストがＲＡＭ１０８に作成される。塗り潰しリストが各グリフ毎に存在する場合、全ての塗り潰しリストを組み合わせることによって、完全なラスタ・イメージをラスタ・バッファに記憶することが可能になる。
【００５４】
理解すべきは、以上の解説は、本発明の単なる例示にすぎないという点である。例えば、グリフを右から左に走査する場合、輪郭勾配が、そのトレーシング方向に基づいて適正に定義されるものと仮定すれば、本方法を同等に適用することが可能である。当該技術の熟練者であれば、本発明を逸脱することなく、さまざまな代替案及び修正を考案することが可能である。従って、本発明は、付属の請求項の範囲内含まれるこうした代替案、修正、及び変更の全てを包含することを意図したものである。
【図面の簡単な説明】
【図１】本発明を実施するようになっているプリント装置の高レベルのブロック図である。
【図２】ラスタ走査線に関する遷移対を記憶する「遷移素子」の略図である。
【図３】図１に示す装置の一部に関する詳細なブロック図である。
【図４】ラスタ走査線とグリフの輪郭との交点を示すグリフの輪郭図である。
【図５】図４に示すグリフの輪郭を処理する際における、図３のブロック図の操作をより深く理解できるようにするチャートである。
【符号の説明】
２０：コントローラ
２２：プリント・エンジン
２４：ＲＯＭ
２６：ＲＡＭ
２８：バス
３０：遷移素子アレイ
３４、３６、３８、４０：記憶領域
５０：遷移素子
５２、５４、５６、５８、６０、６２、６４：記憶位置
６６：制御モジュール
６８：新遷移レジスタ
７０：ＯＮ／ＯＦＦ遷移ラッチ
７２：出力ライン
７４、７６、７８：多重スイッチ
８０、８２、８４：追加多重スイッチ
８６、８８、９０：ＯＦＦからＯＮ記憶位置
９２：遷移素子
９４、９６、９８：ＯＮからＯＦＦ記憶位置
１００：記憶部分
１０２：「ｇｏ  ｔｏ」リンク・レジスタ
１０４：リンク・レジスタ
１０８、１１０、１１２：コンパレータ
１１４、１１６、１１８、１２０：多重スイッチ
１９
【図１】
0003577377.tif 000002
【図２】
0003577377.tif 000003
【図３】
0003577377.tif 000004
【図４】
0003577377.tif 000005
【図５】
0003577377.tif 000006