JPH04262473A - 多重ステッパーを用いた高速図形画像生成法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】本発明は、各々の曲線部分を放物線分に分
け、それらを各ノードが放物線分を定義する樹状のデー
タ構造に変換し、各ノードを一時に１走査線トラバース
して領域全体を埋めるステップからなる曲線線分の図形
対象により定義される領域を埋める方法に関する。

【０００２】殆ど全てのページ記述言語（例：ポストス
クリプト、インタープレスなど）では、ストローク中心
線軌道とストロークの幅で定義される「ストローク」と
、輪郭で定義される「充填領域」という２タイプの図形
対象がある。最初のタイプは実際には第２のタイプに変
換でき、第２のタイプとして処理される。各充填領域の
輪郭は通常、曲線ないし線分のシーケンスとして表現さ
れる。曲線部分は一般的に円錐曲線、円弧、あるいは３
次ベジエ・スプラインとして表現される。プリンタ処理
装置の主要なタスクは先ずそれらの部分を何等かのより
扱いやすい中間形式に変換し、次にそれらの部分で制限
される領域を埋めることである。今日存在している２つ
の典型的な方法として次のものがある。

【０００３】（１）先ず輪郭の各曲線部分を多くの線分
に分ける。第２段階は、その部分（現在純粋に線分で定
義された新たに変換した輪郭で境界をなしている）を４
辺形ないし走査線の集まりに分けることである。第３段
階は次にソフトウエアを実行するないし専用ハードウエ
アでその４辺形を埋めるか走査線を描くことである。こ
の方法はおもに、通常浮動小数点の計算という多くの繰
り返しを通常必要とする曲線分解過程の速度が遅い故に
、性能上問題がある。

【０００４】（２）一時に輪郭の１画素を描き、次にそ
れらの画素で制限される領域を埋める。

【０００５】この方法には２つの問題がある。即ち最初
の問題は、輪郭の領域の外側から内側を判定するのは難
しいことである。第２の問題は、画素を１つ１つ描くの
は非常に時間がかかることである。

【０００６】本発明は図形対象の画像化を３段階に分解
することでなる。第１段階は各曲線部分を放物線及び線
分に分けることである。第２段階はその輪郭（現在放物
線分と線分だけを含む）をＭＳ樹（多重ステッパー樹）
と称する樹状の中間データ構造に変換する。ここでその
木の中の各々のノードは放物線分ないし線分を定義する
。第３段階は各ノードを一時に１走査線「歩進（ｓｔｅ
ｐｐｉｎｇ）」することでＭＳ樹をトラバースし、領域
全体を埋める（異なるエンジンとして実施される）。

【０００７】この方法を取ると少なくとも次の５つの利
点がある。（１）放物線分から線分へ分解する段階をな
くすことができるので、性能が大きく向上する（この段
階はプロセス全体を通して最も時間のかかるプロセスで
ある）。（２）この方法は、元の曲線を放物線ないし線
に分解するため開発されたどのアルゴリズムにも限定さ
れない。即ちアーキテクチャを変えずにより新しく優れ
たアルゴリズムを用いてプロセスを更にスピードアップ
することができる。（３）異なるエンジンの実現は、性
能ないしコストに基づく設計トレードオフに依存し、ソ
フトウエアないしハードウエアのどちらでもよい。 （４）同一方法を用いてクリッパ構造を生成することが
できる。（５）画像のクリッピングを効率的に行うこと
ができる。

【０００８】従来例を図１に示す。全ての曲線は放物線
分ないし線に分けられ、次に区域は輪郭及び回転数で定
義されて埋められる。

【０００９】ステッパーとは、各「ステップ」で特定の
曲線の次の座標を計算し生成することのできる差分エン
ジンとして実現されるハードウエアないしソフトウエア
の一片である。この場合、各ステッパーは曲線（放物線
ないし線）の一片を歩進することができるだけでなく、
一連のそのような曲線を連続的に歩進することができる
。ステッパーは常に低いＸ座標から高いＸ座標へ歩進す
る。

【００１０】輪郭を埋めるには少なくとも２つのステッ
パーが必要である。各ステッパーは低いｘ座標から高い
座標へ伸びた境界を表す。活動ステッパーとは、活性化
され現在歩進しているステッパーである。全てのステッ
パーが同時に活動的である必要はない（即ち一部のステ
ッパーは他よりも遅く出発し、一部のステッパーは他よ
り早く終わる）。全ての活動ステッパーは同期して歩進
する。即ち、各々の活動ステッパーはｘ方向に１画素歩
進して同じ新しいｘ座標に達し、他の全ての活動ステッ
パーがその現在のステップを完了するまでは更に歩進し
ない。充填プロセッサ／プロセスは、各走査線で全ての
活動ステッパーからｙ座標を読み取り、それにより走査
線を埋める。活動ステッパーは各ステップでそのｘ値を
増加し、従って画像は低いｘから高いｘへライン毎に埋
められる。充填性能を向上するため、ステッパーは先ず
その現在のｘ座標値にしたがって分類され、次にその現
在のＹ座標値にしたがって分類される。各走査線が開始
する前に、非活動ステッパーをチェックし、その開始座
標は現在のｘ座標のものと整合するか検査する。ｘ座標
が整合すれば、それらのステッパーは活性化される（実
際の実施では、各走査線に対して一回だけの比較が行わ
れ、どれかのステッパーを活性化する必要があるか判定
される）。活動ステッパーがそのチェーンの最後の部分
の歩進を終了すると、それは不活性化され、破壊される
。全ての活動ステッパーはそのｙ座標にしたがって分類
して、その充填プロセスの性能の向上を図る。輪郭の境
界が互いに交わることがある。この交わりは検出され、
活動ステッパーはそのｙ座標にしたがって再分類される
。頻繁に分類が要求される可能性があることから、ステ
ッパー樹は、輪郭の全てのステッパー・チェーンを指す
ポインタのアレイとして記憶される。分類過程中、その
過程をスピードアップするにはポインタだけを動かせば
よい。ハードウエア実現で特殊なハードウエアを用いて
分類の必要性をなくすこともできる。

【００１１】放物線ステッパーは、放物線分をトレース
する差分エンジンの実施であり、それはペア（ｘとｙ座
標に対する）のスカラー・ステッパーからなっている。 各スカラー・ステッパーは３つのレジスタ（Ｒ０　，Ｒ
１　，Ｒ２　）と２つの加算機構からなっている（図２
ａと２ｂを参照）。次のステッパー演算（ｘに対する２
つの加算とｙに対する２つの加算）は各サイクルに対し
て同時に行われ、ｘ座標が１画素位置進むまで続けられ
る。

【００１２】 Ｒ０　＝Ｒ０　＋Ｒ１　；　　ｘないしｙ軸の画素位置
Ｒ１　＝Ｒ１　＋Ｒ２　：　　ｘないしｙ軸の画素位置
は変化（最初の導出の近似） Ｒ２　＝Ｃ；　　　　　　　　Ｒ１　の変化（定数）（
第２の導出の近似） ここでＲ０　、Ｒ１　、Ｒ２　はそれぞれ出発点、第１
次の差分、第２次の差分である。元の曲線が３次スプラ
インであれば、３次差分がある。

【００１３】それらのレジスタの初期条件は、放物線方
程式に対する初期差であり、次のように導かれる。

【００１４】放物線はパラメトリック方程式で表現され
る。

【００１５】 ＰＡＲ（ｔ）＝Ｐ０　（１−ｔ）２　＋２Ｐ１　ｔ（１
−ｔ）＋Ｐ２　ｔ２　　　ここでＰ０　、Ｐ１　、Ｐ２
　は放物線の制御点である。

【００１６】プロセスは各自にｔ軸に沿って小さい値ｄ
歩進する。

【００１７】 Ｒ０　＝ＰＡＲ（０） ＝Ｐ０　 Ｒ１　＝ＰＡＲ（ｄ）−ＰＡＲ（０） 　　　　＝Ｐ０　（１−ｄ）２　＋２Ｐ１　ｄ（１−ｄ
）＋Ｐ２　ｄ２　−Ｐ０　　　　　＝（（Ｐ２　−Ｐ１
　）−（Ｐ１　−Ｐ０　））ｄ２　＋２（Ｐ１　−Ｐ０
　）ｄＲ２　＝（ＰＡＲ（２ｄ）−ＰＡＲ（ｄ））−（
ＰＡＲ（ｄ）−ＰＡＲ（０））　　　　＝ＰＡＲ（２ｄ
）−２ＰＡＲ（ｄ）＋（ＰＡＲ（０）　　　　＝（Ｐ０
　（１−２ｄ）２　＋４Ｐ１　ｄ（１−２ｄ）＋４Ｐ２
　ｄ２　）−　　　　　　２（Ｐ０　（１−ｄ）２　＋
２Ｐ１　ｄ（１−ｄ）＋Ｐ２　ｄ２　）＋Ｐ０　　　　
　＝２（（Ｐ２　−Ｐ１　）−（Ｐ１　−Ｐ０　））ｄ
２　　　Ｒ１　とＲ２　の絶対値は、各ステップ・サイ
クルについて１画素以上歩進しないように、ｘステッパ
ーに対しては１以下でなければならないことに留意する
。ここでｄの計算が必要になる。放物線の導出物（速度
）は線であるので、放物線の速度の絶対値は、導出した
線の２点の端点の絶対値の最大よりも決して大きくなら
ない。ここでｘ軸に沿った最大速度の絶対値をｖとする
。するとｄを１／ｖとして選ぶと、各段階について、ｘ
座標は決して１画素以上にジャンプしない。更には、ｄ
を１／ｖよりは小さく２−ｋの形で表現できる最大数と
して選ぶと、ｘステッパーのレジスタＲ１　とＲ２　の
端数体の長さが２ｋ「端数」ビットよりも大きければ、
ステッパー演算は単なる整数の加算になり、丸めエラー
はなくなる。Ｒ０　は２ｋ＋ｒビットを必要とする。こ
こでｒは、画素位置をアドレスする必要がある最大座標
のｌｏｇ２　である。 ｙステッパーに対するＲ１　とＲ２　は、１以下の絶対
値を含むよう制限はされない。

【００１８】線ステッパーは放物線ステッパーの特殊な
ケースである（図３ａと３ｂを参照のこと）。線の最初
の導出物は既に定数であるので、Ｒ２　レジスタとＲ１
　に対する加算機構は必要ない（ステッパーに対するハ
ードウエアがあれば、Ｒ２　は単にゼロにセットでき、
ステッパーを単に放物線ステッパーとして作動する）。 ここで線ステッパーの初期値を計算するためにいくつか
の単純化を行う。先ずｘステッパーＲ１　は常に１画素
となるようにセットする（単に１画素をｘ方向に進める
ために）。次にｙステッパーＲ１　レジスタは、整数−
端数の対で表される線の傾きとする。結果が正の数であ
れば、線の最後の点が端点Ｐ１　の望む位置で確実に終
了させるため、合成語が１つ加算される。

【００１９】輪郭に対する境界が多くあるようにステッ
パーも多くある。境界は１方向にのみトラバースする連
結した放物線分ないし線分の集まりである。ここで述べ
るステッパーには、そのｘステッパーとｙステッパーが
含まれている。各ステッパーは境界上の連続部分に対す
る初期値と終了基準を含む一連のノードを接続する連結
フィールドを持っている。図４はあるステッパーとそれ
が連結するノードのデータ構造を示す（２種類のノード
があり、１つは線用、１つは放物線用）。

【００２０】活動ステッパーは、各走査線内で関心座標
を生成する。そこで境界の各対（図５を参照）間の「回
転数」を判定し、そしてそれをその回転数（非ゼロ回転
数あるいは奇数回転数）にしたがってある特定の色ない
しインクで埋める必要がある。各線が出発すると回転数
「ｗ」は０に初期化され、境界を横切ったときにいつで
も方向数「ｄｉｒ」を加えることで更新される。境界が
右に行けばｄｉｒ＝１となり、境界が左に行けばｄｉｒ
＝−１となる。

【００２１】以下はＭＳ樹作成例である。

【００２２】（１）ここで「ａ」点を輪郭が開始する点
とする（この特定例では、輪郭内に軌道は１つしかない
）。部分１は「ｂ」点で終わり右に進む包絡線上の最初
の部分である。ステッパー１はこのように作成され（こ
のステッパーを指しているポインタもポインタのアレイ
に記憶される）、部分１はこのステッパーの最初のノー
ドとして連結される。ステッパー１はｄｉｒ＝１（右へ
）で記される。部分１の制御点は変換されて、ステッパ
ー・パラメータとなり、このノードに記憶される。ステ
ッパー終了パラメータも計算され、このノードに記憶さ
れる。図６ａ，６ｂを参照のこと。

【００２３】（２）包絡線上の次の部分は部分２である
。この部分の方向は左向きに変えられる。この方向変化
は検出されて、ステッパー２を作成するようになり、部
分２はパラメータ化されて、ステッパー・ノードとなり
、ステッパー２に連結される。ステッパー２はｄｉｒ＝
−１（左へ）で記される。図７ａ、７ｂを参照のこと。

【００２４】（３）部分３については、方向の変化はな
いので、新しいステッパーは作成されない。部分３はパ
ラメータ化されてステッパー・ノードになるが、部分２
の後には連結されない。部分３のステッパー・ノードは
その代わりに部分２のステッパー・ノードの前に挿入さ
れる。ステッパーが常に左から右へ歩進するように維持
することが望まれるためである。図８ａ、８ｂを参照の
こと。

【００２５】（４）部分４については、状況は（３）の
ものと同様である。従って、部分４のステッパー・ノー
ドは線ステッパー・ノードの代わりに放物線ステッパー
・ノードであることを除いては手順は同一である。図９
ａ，９ｂを参照のこと。

【００２６】（５）部分５については、この部分の方向
は右に変わる。この方向変化は検出されてステッパー３
を作成するようになり、部分５はパラメータ化されてス
テッパー・ノードとなり、ステッパー３に連結される。 ステッパー３はｄｉｒ＝１（右へ）で記される。図１０
ａ、１０ｂを参照のこと。

【００２７】（６）部分６については、この部分の方向
は左に変わる。この方向変化は検出されてステッパー４
を作成するようになり、部分６はパラメータ化されて、
ステッパー・ノードとなり、ステッパー４に連結される
。ステッパー４はｄｉｒ＝−１（左へ）で記される。 図１１ａ、１１ｂを参照のこと。

【００２８】（７）部分７については、この部分の方向
は右に変わる。この方向変化は検出されて、ステッパー
５を作成するようになり、部分７はパラメータ化されて
、ステッパー・ノードとなり、ステッパー５に連結され
る。ステッパー５はｄｉｒ＝１（右へ）で記される。 図１２ａ、１２ｂを参照のこと。

【００２９】（８）部分８については、この部分の方向
は左に変わる。この方向変化は検出されて、ステッパー
６を作成するようになり、部分８はパラメータ化されて
、ステッパー・ノードとなり、ステッパー６に連結され
る。ステッパー６はｄｉｒ＝−１（左へ）で記される。 図１３ａ、１３ｂを参照のこと。

【００３０】（９）部分９については、方向の変化はな
いので、新しいステッパーは作成されない。部分９はパ
ラメータ化されてステッパー・ノードになるが、部分８
の後には連結されない。部分９のステッパー・ノードは
その代わりに部分８のステッパー・ノードの前に挿入さ
れる。ステッパーが常に左から右へ歩進するように維持
することが望まれるためである。図１４ａ、１４ｂを参
照のこと。

【００３１】（１０）部分１０については、状況は（９
）のものと同様である。従って手順は（９）のものと同
一である。図１５ａ，１５ｂを参照のこと。

【００３２】（１１）この時点で、部分１０は出発点「
ａ」に戻ったことが分かる。ここで最後のステッパー（
ステッパー６）の方向が最初のステッパー（ステッパー
１）の方向と同じかチェックする。この例では方向は異
なり、それはこのプロセスを完了したことを意味する。 方向が同じである場合、それはステッパー１はステッパ
ー６と同一であるべきことを意味する。そこで合成チェ
ーンは左に行くので、２つのステッパー・チェーンを最
後のステッパーのリストの先の最初のステッパーのリス
トと併合しなければならない。

【００３３】ＭＳ樹を通した歩進過程は以下の通りであ
る。

【００３４】（１）第１段階は、全てのステッパーをそ
の最初のノードに記憶された情報と共にロードすること
である。

【００３５】（２）ステッパーはそのｘ座標にしたがっ
て先ず分類される。最低ｘ座標を持つステッパーは活動
ステッパーである（陰影領域として図１６ａから２５ｂ
に示すように）。

【００３６】（３）全ての活動ステッパーをそのｙ座標
にしたがって分類する。

【００３７】（４）全ての活動ステッパーをｘ方向に１
画素進める（各ステッパーに対して１サイクル以上かか
ることがある）。

【００３８】（５）その結果のＹ座標は適切であるかチ
ェックする（即ち境界の交差をチェックする）。境界の
交差が起これば、活動ステッパーをそのＹ座標にしたが
って再分類する。

【００３９】（６）いずれかのステッパーがその終了条
件に達すれば（境界の部分が完了）、次のノードからパ
ラメータをロードする（図１６ａから２５ｂでは、点線
のボックスにより対応するステッパーにロードされたス
テッパー・ノードを示す）。このステッパーに連結する
ノードがなければ、ステッパーを破壊する（境界は完了
）。

【００４０】（７）現在ｘ座標が非活動ステッパーのい
ずれかの初期座標と合致するならば、それらのステッパ
ーを活性化し、ステップ（２）に戻るかステップ（４）
に戻る。全てのステッパーが破壊されれば、終了である
。

【００４１】図１６ａから２５ｂに示す例を用いてその
操作を説明する。

【００４２】（１）図１６ａ、１６ｂは、ロードされ、
最初のノードのパラメータで分類された後のステッパー
構成を示す（それらのノードはロードされた後に廃棄さ
れる）。合計６つのステッパーがあり、その内２つは活
動的である。図１６ａ、１６ｂはまた、「ａ」点と「ｊ
」点の間の区域を歩進している間の状態を示している。 分類後、高速走査方向は下から上であるのでステッパー
６はステッパー１よりも先にあることに注目する。

【００４３】（２）「ｊ」通過点を歩進した後、部分１
０は完結し、部分９はステッパー６にロードされる。図
１７ａ、１７ｂを参照のこと。

【００４４】（３）「ｇ」通過点を歩進した後、更に２
つのステッパーが活性化される。ステッパー４は部分６
に沿って歩進し始め、ステッパー５は部分７に沿って歩
進し始める。ステッパー１とステッパー６は歩進し続け
る。ステッパーはｙ座標上のその位置にしたがって４、
５、６、１の順に分類されることに注目する。図１８ａ
、１８ｂを参照のこと。

【００４５】（４）「ｉ」通過点を歩進した後、部分９
は完了し、部分８はステッパー６にロードされる。図１
９ａ、１９ｂを参照のこと。

【００４６】（５）「ｈ」通過点を歩進した後、ステッ
パー５は部分７の歩進を完了し、ステッパー６は部分８
の歩進を完了する。両方のステッパーはそのステッパー
・ノードを使い果たし、従って終了して破壊される。図
２０ａ、２０ｂを参照のこと。

【００４７】（６）「ｅ」通過点を歩進した後、更に２
つのステッパーが活性化される。ステッパー２は部分４
に沿って歩進し始め、ステッパー３は部分５に沿って歩
進し始める。ステッパー１とステッパー４は歩進し続け
る。ステッパーはｙ座標上のその位置にしたがって４、
３、２、１の順に分類されることに注目する。図２１ａ
、２１ｂを参照のこと。

【００４８】（７）「ｅ」通過点を歩進した後、部分４
は完了し、部分３はステッパー２にロードされる。図２
２ａ、２２ｂを参照のこと。

【００４９】（８）「ｆ」通過点を歩進した後、部分３
は部分５の歩進を完了し、ステッパー４は部分６の歩進
を完了する。両方のステッパーはそのステッパー・ノー
ドを使い果たし、従って終了して破壊される。図２３ａ
、２３ｂを参照のこと。

【００５０】（９）「ｃ」通過点を歩進した後、部分３
は完了し、部分２はステッパー２にロードされる。図２
４ａ、２４ｂを参照のこと。

【００５１】（１０）「ｄ」通過点を歩進した後、全て
のステッパーは破壊され終了する。図２５ａ、２５ｂを
参照のこと。

【００５２】このプロセスはクリッピング機能と共に並
行して使うことができる。手始めに、各ページ・ボディ
の印刷媒体と同じ大きさの矩形のクリッパが最初に存在
すると想定する。クリッピング・オペレータが呼び出さ
れる度に、下層の以前のクリッピング領域と輪郭で定義
される新しいクリッピング領域の共通部分であるクリッ
ピング領域で新しいクリッパが作られる。図２９を参照
のこと。

【００５３】そのクリッパは矩形の集合の集まりとして
表現され、各集合は「ＭＰ」と呼ばれる。各ＭＰは、同
一境界のｘ座標を持つ非重複矩形として定義される。各
ページ・ボディに対する最初のクリッパは、単一矩形か
らなる単一ＭＰからなるクリッパである。クリッパの表
現例については図２６を参照のこと。

【００５４】クリッパ・データ構造の点から、クリッパ
は、クリッパ・ヘッダ・ノードを指すポインタとして表
現される。またクリッパをインタープレス対象（例：軌
道、輪郭など）として容易に扱うことができるように表
現される。クリッパ・フィールドには次の３つの部分体
がある。１）このヘッダ・ノードはクリッパ・ヘッダ・
ノードであると識別するタグ・フィールド、２）このク
リッパ内のＭＰの数を表現するｍｐ　　ｃｎｔフィール
ド、３）ＭＰの集まりを指すポインタのアレイ。

【００５５】各ＭＰは３つのフィールドを持つデータ構
造に記憶される。１）各ＭＰの出発ｘ座標を記憶するｓ
ｔａｒｔ　　ｘ座標フィールド、（各ポリゴンの終了ｘ
座標は、クリッパ・ヘッダ・ノード内のＭＰアレイ内の
次のＭＰのｓｔａｒｔ　　ｘフィールドに記憶される。 ２）各ポリゴン内のラン／矩形の数を表現するｒｕｎ　
　ｃｎｔフィールド。３）ランのアレイとして（ここで
各ランとは、ある特定のｙ座標での垂直の走査線の出発
／終了を指す）。クリッパは複数のクリッピング領域か
らなることがある。各々のクリッピング領域の最後のＭ
Ｐは、それ自身ゼロにセットされたｒｕｎ　　ｃｎｔフ
ィールドを持つＭＰである。各クリッピング領域の最後
のＭＰの出発ｘフィールドは、そのクリッピング領域の
右側境界のｘ座標である。

【００５６】各ランは２つのフィールドを持つデータ構
造に記憶される。１）ランの出発ｙ座標を記憶するｙ　
　ｌｏフィールド、２）ランの終了ｘ座標を記憶するｙ
　　ｈｉフィールドである。図２７と図２８ａ−ｅは、
図２６に示すクリッパ例のデータ構造を示す。

【００５７】以上、本発明は特定の実施例について説明
したが、当技術に熟達した者にとっては本発明の真の趣
旨と範囲から逸脱せずに様々な変更行ったり、その要素
を相当のもので置き換えることができることは理解され
よう。更に本発明の本質的な教示から逸脱せずに多くの
修正を行うことも可能である。

【図面の簡単な説明】

【図１】　　輪郭で制限された領域を埋める段階を示す
。

【図２】　　放物線ステッパー回路を単純化した図式で
ある。

【図３】　　線ステッパー回路を単純化した図式である
。

【図４】　　１つのステッパーのデータ構造とそれに連
結したノードを示す。

【図５】　　回転数のサンプル計算を示す。

【図６】　　例中の部分１のステッパー１の作成を示す
。

【図７】　　例中の部分２のステッパー２の作成を示す
。

【図８】　　後続の部分の扱いを示す。

【図９】　　後続の部分の扱いを示す。

【図１０】　　後続の部分の扱いを示す。

【図１１】　　後続の部分の扱いを示す。

【図１２】　　後続の部分の扱いを示す。

【図１３】　　後続の部分の扱いを示す。

【図１４】　　後続の部分の扱いを示す。

【図１５】　　後続の部分の扱いを示す。

【図１６】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図１７】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図１８】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図１９】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２０】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２１】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２２】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２３】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２４】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２５】　　ＭＳ樹を通して歩進するプロセスを示す
。

【図２６】　　クリッパの表現例である。

【図２７】　　図２６に示すクリッパ例のデータ構造を
示す。

【図２８】　　図２６に示すクリッパ例のデータ構造を
示す。

【図２９】　　クリッピング領域例を示す。

【符号の説明】

Ｒ０　，Ｒ１　，Ｒ２　　　レジスタ、Ｐ０　，Ｐ１　
，Ｐ２　　　制御点

Claims (8)

【特許請求の範囲】
1. 【請求項１】　　制御点及び回転数で定義される曲線、
   放物線ないし線分のリストで定義される輪郭をｘ及びｙ
   座標の集まりに変換するプロセスにあって、制御点とし
   て定義される全ての曲線、放物線、線分を初期座標及び
   高次差分に変換してデータ構造のノードを形成し、現在
   走査線と交差する活動ノードをすべて歩進することで前
   記データ構造を線毎に歩進し、各ノードに対するそのプ
   ロセスは ａ）第１及び高次差分の新しい集合を再計算し、ｂ）次
   のｘ及びｙ座標を再計算することからなる変換プロセス
   。
2. 【請求項２】　　制御点及び回転数で定義される曲線、
   放物線ないし線分のリストで定義される輪郭を充填する
   プロセスにあって、請求項１記載のプロセスを用いてｘ
   及びｙ座標を生成し、前記座標と前記回転数に基づいて
   充填線を生成する充填プロセス。
3. 【請求項３】　　制御点及び回転数で定義される曲線、
   放物線ないし線分のリストで定義される輪郭から矩形の
   集合の集まりからなるクリッパを生成するプロセスにあ
   って、請求項１記載のプロセスを用いてｘ及びｙ座標を
   生成し、前記座標と前記回転数に基づいて矩形を生成す
   るプロセス。
4. 【請求項４】　　前記矩形の生成には、各集合内の全て
   の矩形は同一の幅とｘ座標を持つ矩形の集合の生成が含
   まれる請求項３記載のプロセス。
5. 【請求項５】　　前記各矩形は、同一ｙ座標を持つｘ内
   の連続線の端で定義される点をつなぐ線からなる請求項
   ３記載のプロセス。
6. 【請求項６】　　第１のクリッパは、矩形の集合の集ま
   りで構成され、制御点及び回転数で定義される曲線、放
   物線ないし線分のリストで定義される輪郭から線を生成
   するプロセスにあって、制御点として定義される全ての
   曲線、放物線、線分を初期座標及び高次差分に変換して
   データ構造のノードを形成し、現在走査線と交差する活
   動ノードをすべて歩進することで前記データ構造を線毎
   に歩進し、各ノードに対するそのプロセスはａ）第１及
   び高次差分の新しい集合を再計算し、ｂ）ｘ及びｙ座標
   を再計算し、各々の新しい走査線に対し、前記矩形がス
   テッパー座標間の線と重複する線を生成することからな
   る生成プロセス。
7. 【請求項７】　　前記生成された線は、輪郭を充填する
   のに用いられる請求項６記載のプロセス。
8. 【請求項８】　　前記生成された線は、矩形の集合の集
   まりからなる第２のクリッパを生成するベースとして用
   いられる請求項６記載のプロセス。