JPH10334248A - 印刷処理装置および印刷処理方法 - Google Patents

Abstract

(57)【要約】 【課題】 所定の描画命令で記述されている印刷データ
をディスプレイリストに変換し、ディスプレイリストか
らビットマップ展開する印刷処理において、エッジリス
トデータ生成処理を高速にすることを目的とする。 【解決手段】 印刷データ１を入力する入力手段２と、
入力された印刷データ１から描画オブジェクトの輪郭を
構成するエッジの始点および終点の情報を有したリスト
を生成するリスト生成手段３と、描画オブジェクトのエ
ッジを表す座標点を順次生成する座標点生成手段４と、
その座標点に順序を付けるソート手段５と、印刷出力手
段７と、座標点をその印刷出力手段７で出力可能なデー
タに変換する変換手段６とで構成した。ここで、座標点
生成処理とソート処理とを分離し、先にハードウェア構
成の座標点生成手段４で複数の座標点を繰り返し生成
し、後でソフトウェアのソート手段５でソートすること
で、高速化を実現した。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は印刷処理装置および
印刷処理方法に関し、特に、外部から入力された所定の
描画命令で記述されている印刷データを印刷処理特有の
中間コード（ディスプレイリスト）に変換し、変換され
た中間コードを所定のバンド単位に、あるいはページ単
位にビットマップ展開する印刷処理装置および印刷処理
方法に関する。

【０００２】

【従来の技術】小型、高速のディジタル印刷に適した電
子写真方式のページプリンタの開発に伴い、従来の文字
情報中心の印刷から脱皮した、ラスタ、図形、文字など
を同様に取り扱い、図形、文字等の拡大、回転、変形な
どが自由に制御できる記述言語を用いる印刷処理装置が
一般に普及してきた。この種の記述言語の代表例とし
て、ＰｏｓｔＳｃｒｉｐｔ（Ａｄｏｂｅ Ｓｙｓｔｅｍ
ｓ社商標）、Ｉｎｔｅｒｐｒｅｓｓ（Ｘｅｒｏｘ社商
標）、Ａｃｒｏｂａｔ（Ａｄｏｂｅ Ｓｙｓｔｅｍｓ社
商標）、ＧＤＩ（Ｇｒａｐｈｉｃｓ Ｄｅｖｉｃｅ Ｉ
ｎｔｅｒｆａｃｅ、Ｍｉｃｒｏｓｏｆｔ社商標）等が知
られている。記述言語で作成されている印刷データは、
ページ内の任意の位置のラスタ、図形、文字を表現する
描画命令が任意の順で構成されており、本発明に係わる
ページプリンタで印字するためには、印字前に印刷デー
タをビットマップ展開しなければならない。ビットマッ
プ展開というのは、印刷データをページまたはページの
一部を横切る一連の個々のドットまたは画素へ展開して
ラスタ走査線を形成し、そのページの下へ引き続く走査
線を次々に発生する過程である。

【０００３】記述言語で作成されている印刷データの
内、図形あるいは文字に関する描画命令を、それが表現
する描画オブジェクトの輪郭を構成するエッジ情報を含
んだリストを複数個連結させたディスプレイリストに変
換した後、そのディスプレイリストをビットマップ展開
することにより印刷処理を行う方法が一般的に知られて
いる。このような印刷処理方法として、例えば特開平６
−３０５２０３号公報、特開平７−１７５６０４号公報
等が公知である。

【０００４】また、ディスプレイリストからビットマッ
プデータへ展開する方法は、文献「実践コンピュータグ
ラフィックス」（Ｄａｖｉｄ Ｆ． Ｒｏｇｅｒｓ著、
山口富士夫監修、１９８７年、日刊工業新聞社発行、ｐ
ｐ８４−９６）に記載されたものがある。

【０００５】上記文献に記載された図形あるいは文字の
輪郭情報と上記ディスプレイリストの関係、ディスプレ
イリストからビットマップ展開のためのエッジの座標点
を生成する処理の流れを図４９に示す。

【０００６】図４９は輪郭情報からビットマップ展開の
ためのエッジの座標点を生成するまでの流れを示す説明
図である。図４９の例において、多角形の輪郭は四つの
エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄから構成されている。こ
れらのエッジＥａ，Ｅｂ，Ｅｃ，Ｅｄは、それらの絶対
値の小さい方の頂点（以下エッジの始点と呼ぶ）のｙ座
標値によりソートされ、ｙバケットリストに連結されて
記憶されている。例えば、エッジＥａ，Ｅｂの始点（ｘ
１，ｙ１）を交差する走査ラインでは、ｙ１の座標値に
対応するｙバケットリストに、エッジＥａの情報を表す
セルとエッジＥｂの情報を表すセルとが記憶されてい
る。ｙバケットリストの各セルは、走査ラインと各エッ
ジの交点を発生させるための情報、すなわち、エッジの
始点のｘ座標値と、エッジの傾きを表す走査ライン当た
りのｘの変化量Δｘと、エッジと走査ラインとの交差数
Δｙと、次のセルへのポインタとを含んでいる。ｙバケ
ットリストおよび各セルを含む全体をディスプレイリス
トと呼ぶ。次に、このディスプレイリストから各走査ラ
イン毎に同時に処理しなければならない情報に変換され
る。これをアクティブエッジリストと呼ぶ。そして、こ
のアクティブエッジリストからエッジの座標点が出力さ
れることになる。

【０００７】一般的にディスプレイリストからエッジの
座標点を生成する処理は走査ライン変換と呼ばれる。走
査ライン変換によって生成されたエッジの座標点を座標
値によりソートし、ソートされた座標点間を所定の色デ
ータで順次塗りつぶし処理を施したものがビットマップ
データである。走査ライン変換は、１走査ラインずつ、
上部から下部までのエッジの座標点を発生する。すなわ
ち、現在の走査ラインと交わる全エッジをリスト化し
て、図４９に示すアクティブエッジリストを作成しなが
らエッジの座標点を出力する。現在の走査ラインの処理
後、アクティブエッジリストの各レコードは次走査のた
めに更新（ｘ＝ｘ＋Δｘ，Δｙ＝Δｙ−１）される。Δ
ｙ＝０になったバケットは、リストから削除される。

【０００８】

【発明が解決しようとする課題】上記特開平６−３０５
２０３号公報、特開平７−１７５６０４号公報等は、デ
ータ量の少ないディスプレイリストを印刷処理のための
中間データとし、印字装置の印字出力に応じて バンド
単位でビットマップ展開することにより、ビットマップ
展開のための大容量のフレームバッファメモリの削減を
狙ったものである。しかし、特開平６−３０５２０３号
公報、特開平７−１７５６０４号公報では、上記ディス
プレイリストからビットマップデータへの展開は、ソフ
トウェア処理で行われており、高速の印刷処理装置には
適用できないという問題点があった。これは、記述言語
で作成される印刷データでは、一つの描画命令で記述さ
れる描画オブジェクトの複雑さに制限がないため、上述
した走査ライン変換あるいはエッジの座標点のソート処
理を専用のハードウェアで高速化しようとすると、その
複雑さに対応した数の同時処理が必要になり、大規模な
ハードウェアを用意する必要があるためである。

【０００９】一方、コンピュータグラフィックスをディ
スプレイ上に表示する技術分野においては、図形の輪郭
を表現する多角形データのディスプレイリストを単純な
三角形データのディスプレイリストや台形データのディ
スプレイリストに分割した後、専用ハードウェアを用い
て高速にビットマップ展開する処理が行われている。例
えば、三角形データ分割に関しては特開平７−１６０８
９９号公報等、台形データ分割に関しては特開平４−１
４１８９号公報等が公知である。すなわち、コンピュー
タグラフィックスの技術分野においては、一つの描画命
令で記述される描画オブジェクトの複雑さに制限を設け
ハードウェアで高速処理を行っている。これは、コンピ
ュータグラフィックスの技術分野における図形の輪郭を
表現する多角形は、一般に凸多角形で表現されており、
三角形や台形への分割が容易であるためである。しかし
ながら、記述言語で作成される図形要素では、エッジが
交差する場合も発生するため、三角形や台形への分割に
は多大な計算を必要とする。

【００１０】図５０はエッジが交差する図形要素の例を
示した図である。図５０に示す図形要素は七つのエッジ
Ｅｅ，Ｅｆ，Ｅｇ，Ｅｈ，Ｅｉ，Ｅｊ，Ｅｋからなり、
この図形要素の中を塗りつぶすものとする。この塗りつ
ぶしは走査ラインと交差するエッジの座標点に挟まれた
間で行われる。エッジＥｉ，Ｅｊのように交差している
ところでは、例えばエッジＥｅとエッジＥｊとに挟まれ
た領域ａを塗りつぶしていくと、途中でエッジＥｅとエ
ッジＥｉとに挟まれた領域ｂの塗りつぶしに入れ替わ
る。つまり、エッジの交差する部分でエッジの並べ替え
などの処理が発生する。このため、三角形や台形への分
割にはこのような処理があらかじめなされていることが
必要であり、多大な計算を必要とし、システム全体とし
てハードウェア処理の高速性を十分に活かすことはでき
ない。したがって、コンピュータグラフィックスの技術
分野におけるハードウェア処理を、記述言語で作成され
ている印刷データを処理する印刷処理の技術分野に適用
することはできない。

【００１１】本発明は、このような点に鑑みてなされた
ものであり、図形や文字に関する描画命令を、それが表
現する描画オブジェクトの輪郭を構成するエッジ情報を
含んだディスプレイリストに変換し、そのディスプレイ
リストをビットマップ展開する印刷処理装置において、
大規模なハードウェアを用意することなく、さらに、複
雑な描画オブジェクトを三角形や台形からなるディスプ
レイリストに分割するために多大な計算を必要とするこ
となく、高速にビットマップ展開することを可能とする
印刷処理装置および印刷処理方法を提供することを目的
とする。

【００１２】

【課題を解決するための手段】本発明では上記問題を解
決するために、文字または図形に関する描画命令を印刷
画像データに変換して印刷出力する印刷処理装置におい
て、所定の描画命令で記述された少なくとも文字または
図形のいずれかの描画オブジェクトを有する印刷データ
を入力する入力手段と、前記入力手段に入力された前記
印刷データから前記描画オブジェクトの輪郭を構成する
エッジの始点および終点の情報を有したリストを前記描
画オブジェクト毎に生成するリスト生成手段と、前記リ
スト生成手段で生成された前記リストの前記始点および
終点の情報から前記描画オブジェクトの前記エッジを表
す座標点を順次生成する座標点生成手段と、前記座標点
生成手段で生成された前記座標点に順序を付けるソート
手段と、前記描画オブジェクトの印刷画像データを印刷
出力する印刷出力手段と、前記ソート手段で決定された
順番の前記座標点を前記印刷出力手段で出力可能な印刷
画像データに変換する変換手段と、を備えていることを
特徴とする印刷処理装置が提供される。

【００１３】このような印刷処理装置によれば、入力手
段に入力された印刷データは、リスト生成手段に渡さ
れ、ここで、印刷データに指示された描画オブジェクト
の輪郭を構成するエッジの始点および終点の情報を描画
オブジェクト毎に有したリストを生成する。次にこのリ
スト情報を基に、描画オブジェクトのエッジを表す座標
点をある順序に従って生成するが、本発明による印刷処
理装置では、この部分の処理を座標点生成手段およびソ
ート手段で分けて行うように構成したことを特徴として
いる。すなわち、まず、座標点生成手段を複数の座標点
生成装置で構成し、これら複数の座標点生成装置がリス
ト情報から描画オブジェクトのエッジを表す座標点を専
ら生成するよう繰り返し処理し、複数の座標点を一度に
生成する。座標点生成装置で生成された座標点はソート
手段にて順序付けされる。そして、順序付けされた座標
点は変換手段にて印刷出力手段が出力可能な印刷画像デ
ータに変換される。このようにして、座標点生成および
順序付けの処理を独立させたことにより、それぞれの処
理に適した処理資源を適用することができ、座標点生成
に関して高速に処理することが可能になる。

【００１４】また、本発明によれば、文字または図形に
関する描画命令を印刷画像データに変換して印刷出力す
る印刷処理方法において、所定の描画命令で記述された
少なくとも文字または図形のいずれかの描画オブジェク
トを有する印刷データを入力し、前記描画オブジェクト
の輪郭を構成するエッジの始点および終点の情報を有し
たリストを前記描画オブジェクト毎に生成し、前記リス
トの前記始点および終点情報から前記描画オブジェクト
の前記エッジを表す座標点を一度に複数生成し、生成さ
れた前記座標点に順序を付け、順序付け工程で決定され
た順番の前記座標点情報を最終的に印刷出力される画像
データに変換する、ことからなることを特徴とする印刷
処理方法が提供される。

【００１５】この印刷処理方法では、入力された印刷デ
ータから描画オブジェクト毎にリストを生成した後、ま
ず、リストの始点および終点の情報から描画オブジェク
トのエッジを表す座標点を一度に複数生成し、次に、生
成された座標点に順序付けを行う。つまり、座標点の生
成と座標点の順序付けとを別個に行うようにしている。
そして、順序付けされた座標点の情報から印刷出力装置
が出力可能な画像データへの変換が行われる。このよう
に、座標点の生成工程が座標点の順序付けと独立に行わ
れるので、この工程を座標点生成に適した処理資源によ
り実施することにより、印刷データを入力してから印刷
出力装置が出力可能な画像データへの変換までの印刷処
理を高速に行うことができる。

【００１６】

【発明の実施の形態】以下、本発明の実施の形態を図面
を参照して説明する。図１は本発明による印刷処理装置
の原理的な構成を示す図である。図１において、印刷処
理装置は、所定の描画命令で記述された少なくとも文字
または図形のいずれかの描画オブジェクトを有する印刷
データ１を入力する入力手段２と、入力手段２に入力さ
れた印刷データ１から描画オブジェクトの輪郭を構成す
るエッジの始点および終点の情報を描画オブジェクト毎
に有したリストを生成するリスト生成手段３と、リスト
生成手段３で生成されたリストの始点および終点の情報
から描画オブジェクトのエッジを表す座標点を順次生成
する座標点生成手段４と、この座標点生成手段で生成さ
れた座標点に順序を付けるソート手段５と、印刷データ
１を出力する印刷出力手段７と、ソート手段５で決定さ
れた順番の座標点を用いて印刷データ１を印刷出力手段
７で出力可能なデータに変換する変換手段６とから構成
されている。

【００１７】ここで、座標点生成手段４は、複数の座標
点生成装置で構成され、座標点生成装置の数と同数の座
標点を一度に生成するよう構成されている。さらに好ま
しくは、複数の座標点生成装置はハードウェアで構成さ
れ、ソート手段は、所定のプログラムを中央演算処理装
置で実行することにより座標点の順序付けを行うよう構
成されている。

【００１８】上記構成において、本発明は、描画オブジ
ェクトの輪郭を構成するエッジの始点および終点の情報
を描画オブジェクト毎に有したリスト情報から、描画オ
ブジェクトのエッジを表す座標点を生成する座標点生成
処理と、座標点に順序を付けるソート処理とを独立さ
せ、それぞれの処理に適した処理資源で処理されるよう
構成したことを特徴としている。すなわち、座標点生成
処理に関しては、座標点生成手段４の複数の座標点生成
装置で繰り返し座標点生成のみを行うよう構成すること
ができ、従来のハードウェアのみで座標点生成処理とソ
ート処理とを行っていた場合に比較して、大規模なハー
ドウェアを用意したり、印刷データを制限されたハード
ウェア量に合わせたリストデータに変換するための前処
理に多大な処理時間を費やす必要がなくなる。また、従
来のソフトウェア処理のみで座標点生成処理とソート処
理を行っていた場合に比較して、ソフトウェア処理では
多大な計算時間を必要する座標点生成処理を、ハードウ
ェアで並列かつパイプライン構成により、高速に処理す
ることができるため、全体として高速化が可能となる。

【００１９】したがって、図形や文字に関する描画命令
を、それが表現する描画オブジェクトの輪郭を構成する
エッジ情報を含んだディスプレイリストに変換し、その
ディスプレイリストをビットマップ展開する印刷処理装
置に本発明を適用することにより、大規模なハードウェ
アを用意することなく、さらに、複雑な描画オブジェク
トを三角形や台形からなるディスプレイリストに分割す
るために多大な計算を必要とすることなく、高速にビッ
トマップ展開することが可能となる。

【００２０】図２は本発明の印刷処理装置の全体的な構
成を示すブロック図である。図２において、印刷処理装
置は、印刷データスプール部１０と、印刷データ解釈部
１１と、ディスプレイリスト生成部１２と、バンド分割
部１３と、ラスタデータ処理部１４と、ラスタデータバ
ッファ１５と、ディスプレイリストバッファ１６と、デ
ィスプレイリストバンドバッファ１７と、ディスプレイ
リスト管理部１８と、座標点生成部１９と、ソート部２
０と、エッジリストバッファ２１と、印刷画像データ変
換部２２と、ラスタデータバンドバッファ２３と、出力
バッファ２４と、プリンタ装置制御部２５と、プリンタ
装置２６とから構成されている。以下、この印刷処理装
置の各構成要素の概要および動作について説明する。

【００２１】図２において、印刷データ１は印刷処理装
置で処理可能な記述言語で記述されたものであり、図示
されないパーソナルコンピュータやワークステーション
において、文書作成や編集等を処理するアプリケーショ
ンプログラムで作成された文書データから生成されたも
のである。本実施例で対象とする記述言語は、例えばＧ
ＤＩであるが、Ａｃｒｏｂａｔで代表されるＰＤＦ（Ｐ
ｏｒｔａｂｌｅ Ｄｏｃｕｍｅｎｔ Ｆｏｒｍａｔ）、
ＰｏｓｔＳｃｒｉｐｔで代表されるページ記述言語であ
ってもよい。

【００２２】印刷データスプール部１０は、印刷データ
１を入力するための通信機能や、印刷データ解釈部１１
へ出力されるまで印刷データを一時的に記憶する機能等
を備えたものである。

【００２３】印刷データ解釈部１１は、印刷データスプ
ール部１０より入力された印刷データを、定められた記
述言語のシンタックスに従ってトークンとして切り出し
た後、そのトークンを解釈し、内部命令やその引数に変
換する。内部命令には、文字／図形／ラスタの描画を実
行する描画命令や、色や線属性など描画に必要な情報を
設定する描画状態命令がある。描画命令が文字あるいは
図形の場合は、描画命令をディスプレイリスト生成部１
２へ転送する。一方、描画命令がラスタの場合は、描画
命令をラスタデータ処理部１４へ転送するとともに、対
象とするラスタデータの縦および横の大きさを表す情報
をディスプレイリスト生成部１２へ転送する。

【００２４】ディスプレイリスト生成部１２は、文字／
図形の描画命令に応じて、描画されるオブジェクトの輪
郭を構成するエッジデータを生成した後、オブジェクト
毎にヘッダ情報と、描画オブジェクトの輪郭を構成する
エッジの始点、傾きおよびエッジと走査ラインとの交差
数を含むエッジ情報とから構成されるディスプレイリス
トを生成する。また、印刷データ解釈部１１より転送さ
れたラスタデータの縦および横の大きさに基づき、ラス
タデータの輪郭を示すディスプレイリストを生成する。

【００２５】バンド分割部１３は、ディスプレイリスト
生成部１２で生成された描画オブジェクト毎のディスプ
レイリストを１ページ分を所定のバンド数で分割したと
きのバンド単位で分割する。バンドの分割数は、後段の
出力バッファ２４の大きさで決定される。バンド単位で
分割されたディスプレイリストは、ディスプレイリスト
バッファ１６に格納される。印刷データ解釈部１１から
バンド分割部１３までの処理を、ページを構成するすべ
ての描画オブジェクトに対して実行することにより、バ
ンド単位で分割されたディスプレイリストがページ毎に
ディスプレイリストバッファ１６に格納される。

【００２６】ラスタデータ処理部１４は、ラスタの描画
命令に応じて、対象とするラスタデータに対し座標変
換、色補正等のラスタ処理を実行し、処理されたラスタ
データはラスタデータバッファ１５に格納される。

【００２７】ディスプレイリストバンドバッファ１７
は、二つのバッファで構成され、ディスプレイリストバ
ッファ１６からディスプレイリストデータがバンド単位
で交互に入力される。

【００２８】ディスプレイリスト管理部１８は、ディス
プレイリストバンドバッファ１７からのディスプレイリ
ストの読み出しと、後段の座標点生成部１９が待機状態
にあることの検出と、検出結果に基づき座標点生成部１
９へディスプレイリストのエッジ情報の転送を制御する
ものである。また、ディスプレイリスト管理部１８で
は、ヘッダ情報に基づき処理するオブジェクトのタイプ
が文字／図形かまたはラスタかを検出し、ラスタの場合
は、印刷画像データ変換部２２に指示して、当該オブジ
ェクトのラスタデータをラスタデータバッファ１５から
ラスタデータバンドバッファ２３に転送する。

【００２９】座標点生成部１９は、エッジの始点、傾き
およびエッジと走査ラインとの交差数を含むエッジ情報
から、走査ライン毎にエッジの座標点をエッジリストバ
ッファ２１に出力するものであり、複数の座標点生成回
路で構成され、座標点生成回路の数と同数のエッジの座
標点を一度に出力する。複数の座標点生成回路は、走査
ライン毎に複数のエッジに対する座標点生成を実行す
る。処理中のすべてのエッジに対する処理が終了する
と、ディスプレイリスト管理部１８より次に処理すべき
複数のエッジ情報が転送される。一つのオブジェクトに
対するすべてのエッジの座標点生成が終了するまで、複
数の座標点生成回路による座標点生成が繰り返される。
また、処理するオブジェクトが文字／図形の場合は、ヘ
ッダ情報に基づき処理するオブジェクトの色データがエ
ッジリストバッファ２１に格納される。

【００３０】ソート部２０は、座標点生成部１９による
一つのオブジェクトに対するすべてのエッジの座標点生
成が終了した後、エッジリストバッファ２１に格納され
ている走査ライン毎のエッジ座標点データを、座標値の
小さいものから順次整列するよう並べ替える処理を行う
ものであり、所定のプログラムを中央演算処理装置で実
行する構成となっている。ソート処理のためのプログラ
ムとしては、例えばクイックソートプログラムが用いら
れる。

【００３１】印刷画像データ変換部２２は、エッジリス
トバッファ２１の座標値の小さいものから順次整列する
よう並べかえられたエッジの座標点のペアの間の塗りつ
ぶし処理を行い、出力バッファ２４に出力するものであ
る。処理するオブジェクトが文字／図形の場合は、エッ
ジリストバッファ２１に格納されている色データにより
塗りつぶし処理を実行する。処理するオブジェクトがラ
スタデータの場合は、ラスタデータバンドバッファ２３
よりエッジの座標点のペアの間を埋めるラスタデータを
読み出し、出力バッファ２４に出力する。なお、エッジ
リストバッファ２１も二つのバッファで構成され、座標
点生成処理およびソート処理と、印刷画像データ変換処
理はパイプラインで実行可能に構成されている。

【００３２】出力バッファ２４は、二つのバッファで構
成され、一方のバッファが印刷画像データ変換部２２に
より塗りつぶし処理が行われている間、他方のバッファ
は、後段のプリンタ装置制御部２５を介して、プリンタ
装置２６へ印刷画像データが転送されるよう構成されて
いる。

【００３３】プリンタ装置制御部２５は、プリンタ装置
２６の出力タイミングに応じて出力バッファ２４の印刷
画像データをプリンタ装置２６へ転送するとともに、プ
リンタ装置２６の状態制御および管理を実行するもので
ある。

【００３４】プリンタ装置２６は、プリンタ装置制御部
２５の制御に基づき、出力バッファ２４から出力される
印刷画像データを受け取って、記録用紙に印字し出力す
るものである。さらに、詳しくは、このプリンタ装置２
６は、ＣＭＹＢｋ（シアン、マゼンタ、イエロー、ブラ
ック）カラーの色毎に露光、現像、転写を繰り返すこと
によりフルカラー画像を出力できるレーザ走査方式の電
子写真方式を用いたカラーページプリンタである。

【００３５】なお、この構成例はディスプレイリストが
所定のバンド単位に分割され、バンド単位で処理される
ことを前提に記載されているが、これに限定されるもの
ではなく、ページ単位で処理される構成であってもよ
い。

【００３６】次に上述したように構成された印刷処理装
置における印刷処理の流れの概要について、図３を用い
て説明する。図３は印刷処理装置における印刷処理の流
れを示すフローチャートである。まず、文字または図形
を含む印刷データ１が印刷データスプール部１０に入力
されると、印刷データ解釈部１１、ディスプレイリスト
生成部１２、バンド分割部１３を介してディスプレイリ
ストが生成され、少なくとも１ページ分のバンド分割さ
れたディスプレイリストがディスプレイリストバッファ
１６に格納される（ステップＳ１）。次に、ディスプレ
イリストがディスプレイリストバッファ１６よりバンド
単位で順次ディスプレイリストバンドバッファ１７に入
力される（ステップＳ２）。

【００３７】次に、ディスプレイリスト管理部１８にお
いて、最初のオブジェクトのディスプレイリストのエッ
ジ情報が、最大で座標点生成部１９の有する座標点生成
回路の数だけ座標点生成部１９に転送される（ステップ
Ｓ３）。座標点生成部１９では、座標点の生成（ステッ
プＳ４）、走査ラインの更新（ステップＳ５）、すべて
の座標点生成回路の待機状態のチェック（ステップＳ
６）が行われる。もし、すべての座標点生成回路が待機
状態でなければ、ステップＳ４、ステップＳ５、ステッ
プＳ６を繰り返す。もし、すべての座標点生成回路が待
機状態になれば、オブジェクトのすべてのエッジの処理
終了のチェック（ステップＳ７）が行われる。もし、当
該オブジェクトのすべてのエッジの処理が終了していな
ければ、ステップＳ３で次のエッジ情報が最大で座標点
生成部１９の有する座標点生成回路の数だけ座標点生成
部１９に転送され、ステップＳ４以下の処理が繰り返さ
れる。もし、当該オブジェクトのすべてのエッジの処理
が終了していれば、ソート部２０によるソート処理が実
行され（ステップＳ８）、続いて印刷画像データ変換部
２２による印刷画像データへの変換処理および変換され
た印刷画像データの出力バッファ２４への出力が実行さ
れる（ステップＳ９）。

【００３８】次に、バンド内のすべてのオブジェクト処
理終了のチェックが行われる（ステップＳ１０）。も
し、当該バンドのすべてのオブジェクトの処理が終了し
ていなければ、ステップＳ３に戻り、次のオブジェクト
の最初のエッジ情報が、最大で座標点生成部１９の有す
る座標点生成回路の数だけ座標点生成部１９に転送さ
れ、ステップＳ４以下の処理が繰り返される。もし、当
該バンドのすべてのオブジェクトの処理が終了していれ
ば、プリンタ装置制御部２５を介してプリンタ装置２６
に印刷画像データの出力が行われる（ステップＳ１
１）。

【００３９】次に、ページ内のすべてのバンド処理終了
のチェックが行われる（ステップＳ１２）。もし、当該
バンドのすべてのオブジェクトの処理が終了していなけ
れば、ステップＳ２以下の処理が繰り返される。もし、
当該バンドのすべてのオブジェクトの処理が終了してい
れば、１ページ分の印刷処理は終了する。処理する印刷
データが複数ページあれば、上記処理を複数ページ分繰
り返す。

【００４０】なお、上記印刷処理の流れの説明では、簡
単にするため、ラスタデータ処理に関する記載は省略し
たが、ラスタデータ処理に関しては各構成要素の概要お
よび動作で説明したように処理される。

【００４１】次に、印刷処理装置が実装されるコンピュ
ータシステムの二つの構成例を以下に示す。図４は印刷
処理装置全体が実装されるコンピュータシステムのハー
ドウェア構成例を示した図である。図４において、コン
ピュータシステムは、ホストコンピュータ３０と、ホス
トコンピュータ３０が接続されるネットワーク４１と、
ホストコンピュータ３０に装着される描画処理カード３
８と、プリンタ装置２６と、描画処理カード３８とプリ
ンタ装置２６とを接続する専用バス４２とで構成されて
いる。ネットワーク４１は、例えばイーサネット（Ｅｔ
ｈｅｒｎｅｔ）であり、ネットワーク４１を介して図示
しないパーソナルコンピュータ、ワークステーション等
から印刷データ１が入力される。ホストコンピュータ３
０は、ＣＰＵ（中央演算処理装置）３１と、メモリコン
トローラ３２と、ＤＲＡＭ（ｄｙｎａｍｉｃ ｒａｎｄ
ｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）３３と、システム
バスコントローラ３４と、ネットワークインタフェース
３５と、磁気ディスク３６と、カードコントローラ３７
と、ＣＰＵバス３９と、システムバス４０とから構成さ
れる一般的なものである。

【００４２】システムバス４０は、例えばＰＣＩ（ｐｅ
ｒｉｐｈｅｒａｌ ｃｏｍｐｏｎｅｎｔ ｉｎｔｅｒｃ
ｏｎｎｅｃｔ）バスであり、カードコントローラ３７は
高速のデータ転送が可能なカードバス（ＣａｒｄＢｕ
ｓ）対応のコントローラである。ホストコンピュータ３
０には、本印刷処理装置の印刷データスプール部１０、
印刷データ解釈部１１、ディスプレイリスト生成部１
２、バンド分割部１３、ラスタデータ処理部１４、ラス
タデータバッファ１５、ディスプレイリストバッファ１
６に相当する機能が実装される。例えば、磁気ディスク
３６は、印刷データ解釈部１１、ディスプレイリスト生
成部１２、バンド分割部１３、ラスタデータ処理部１４
の各処理のための所定のプログラム等の格納領域、印刷
データスプール部１０の印刷データ格納領域として使用
される。また、ＤＲＡＭ３３は、印刷データ解釈部１
１、ディスプレイリスト生成部１２、バンド分割部１
３、ラスタデータ処理部１４の各処理のためのワークエ
リア、ラスタデータバッファ１５、ディスプレイリスト
バッファ１６として使用される。さらに、ＣＰＵ３１は
印刷データ解釈部１１、ディスプレイリスト生成部１
２、バンド分割部１３、ラスタデータ処理部１４の各処
理のための所定のプログラムを実行する。

【００４３】図５は描画処理カードのハードウェア構成
例を示した図である。図５において、描画処理カード３
８は、ホストコンピュータ３０のＣＰＵとは異なる第２
のＣＰＵ５０と、カードインタフェース５１と、フラッ
シュＲＯＭ（ｒｅａｄ ｏｎｌｙ ｍｅｍｏｒｙ）５２
と、メモリコントローラ５３と、メモリ５４と、座標点
生成ＬＳＩ（大規模集積回路）５５と、印刷画像データ
変換ＬＳＩ５６と、出力バッファメモリ５７と、ラスタ
データバンドバッファメモリ５８と、プリンタ制御ＬＳ
Ｉ５９と、ビデオインタフェース６０と、カード内部バ
ス６１とから構成されている。この描画処理カード３８
には、本印刷処理装置のディスプレイリストバンドバッ
ファ１７、ディスプレイリスト管理部１８、座標点生成
部１９、ソート部２０、エッジリストバッファ２１、印
刷画像データ変換部２２、ラスタデータバンドバッファ
２３、出力バッファ２４、およびプリンタ装置制御部２
５の機能が実装されている。例えばフラッシュＲＯＭ５
２はソート部２０のソート処理のための所定のプログラ
ム等が格納されるとともに、オペレーティングシステム
のプログラムが格納される。メモリ５４は、例えばＤＲ
ＡＭで構成され、ソート処理のためのプログラム実行の
ためのワークエリア、ディスプレイリストバンドバッフ
ァ１７、エッジリストバッファ２１として使用される。
また、座標点生成ＬＳＩ５５にはディスプレイリスト管
理部１８と座標点生成部１９の機能、印刷画像データ変
換ＬＳＩ５６には印刷画像データ変換部２２の機能、プ
リンタ制御ＬＳＩ５９およびビデオインタフェース６０
はプリンタ装置制御部２５の機能がそれぞれ実装されて
いる。さらに、第２のＣＰＵ５０はソート部２０のソー
ト処理のための所定のプログラムの実行、ディスプレイ
リストバンドバッファ１７へのディスプレイリスト入力
の制御、出力バッファメモリ５７やラスタデータバンド
バッファメモリ５８のメモリクリアの制御等を実行す
る。また、出力バッファメモリ５７およびラスタデータ
バンドバッファメモリ５８は、例えばＤＲＡＭで構成さ
れる。

【００４４】ディスプレイリストバンドバッファ１７以
降の処理機能を独立した１枚の描画処理カードの回路基
板上に一体に実装することにより、カード内部バス６１
はホストコンピュータ３０のシステムバス４０とは独立
に設けることが可能になり、バスの競合によるデータ転
送速度低下を低減することができる。さらに、ホストコ
ンピュータ３０のシステムバス４０より高速のバスを設
けることにより、データ転送の高速化が可能となる。ま
た、図５の構成において、出力バッファメモリ５７およ
びラスタデータバンドバッファメモリ５８は、カード内
部バス６１を介さず直接印刷画像データ変換ＬＳＩ５６
に接続された構成をとっている。このような構成をとる
ことにより、データ転送のボトルネックを解消し、より
高速のデータ転送が可能となる。また、第２のＣＰＵ５
０の主要な処理はソート処理に限定されるため、ホスト
コンピュータ３０のＣＰＵ３１に比較して、性能の低い
ＣＰＵを使用することが可能であり、図５に示すような
カード化が可能である。また、ディスプレイリストバン
ドバッファ１７以降の処理機能をカード化したことによ
り、ディスプレイリストバンドバッファ１７までの処理
機能を持つホストコンピュータ３０とは着脱自在な形態
になっている。

【００４５】図６は印刷処理装置全体が実装される他の
コンピュータシステムのハードウェア構成例を示した図
である。図６において、図４と同じ構成要素については
同じ符号を付して詳細な説明は省略する。図６に示した
コンピュータシステムは、図４に示した構成ではディス
プレイリストバンドバッファ１７以降の処理を実装する
描画処理カード３８がホストコンピュータ３０に直接接
続されているのに対し、ディスプレイリストバンドバッ
ファ１７以降の処理を実装する描画処理ボード４５がシ
リアルバス４４を介してプリンタ装置２６に直接接続さ
れている。このため、ホストコンピュータ３０にはシリ
アルバスインタフェース４３が設けられている。この描
画処理ボード４５もディスプレイリストバンドバッファ
１７以降の処理機能を独立した１枚の回路基板上に一体
に実装され、ディスプレイリストバンドバッファ１７ま
での処理機能と着脱可能になっている。

【００４６】図７は描画処理ボードのハードウェア構成
例を示した図である。図７において、図５と同じ構成要
素については同じ符号を付して詳細な説明は省略する。
図７に示した描画処理ボード４５は、シリアルバスイン
タフェース６２が設けられている点で図５の構成と異な
るが、その他の構成要素および機能は図５のものと同一
である。シリアルバス４４は、例えばＩＥＥＥ（米国電
気電子技術者協会）１３９４高性能シリアルバスであ
る。このＩＥＥＥ１３９４高性能シリアルバスを設ける
ことにより、処理性能を低下させることなく、プリンタ
装置２６およびホストコンピュータ３０の配置構成を自
由に設定することが可能となる。

【００４７】以上、本発明の印刷処理装置の概要につい
て記述した。次に、この印刷処理装置の主要部の詳細に
ついて説明する。初めに、印刷データ解釈部１１につい
て詳細に説明する。

【００４８】図８は印刷データ解釈部の構成を示すブロ
ック図である。図８において、印刷データ解釈部１１
は、字句解析部１１１と、トークン解釈部１１２と、命
令実行部１１３と、描画状態記憶部１１４とから構成さ
れている。

【００４９】字句解析部１１１は、印刷データスプール
部１０から入力された印刷データを定められた記述言語
のシンタックスに従ってトークンとして切り出し、その
トークンをトークン解釈部１１２に出力するものであ
る。トークン解釈部１１２は、字句解析部１１１から入
力されたトークンを解釈し、内部命令やその引数に変換
し、それら内部命令と引数との組を命令実行部１１３へ
転送する。内部命令には、例えば文字／図形／ラスタの
描画を実行する描画命令や、色や線属性など描画に必要
な情報を設定する描画状態命令などがある。

【００５０】命令実行部１１３は、トークン解釈部１１
２から送られてきた内部命令を実行する。ここで実行す
る命令は、主に描画命令と描画状態命令とがある。例え
ば描画命令には、以下の表１に示すように３種類の描画
命令があり、それぞれの描画に必要な情報が示されてい
る。このうちアンダーラインがある情報については、描
画命令中の引数として与えられ、その他の情報は予め初
期設定や先行する命令などにより描画状態記憶部１１４
に記憶されている。描画命令の実行は、ラスタ描画以外
は受け取った描画命令をそのままディスプレイリスト生
成部１２へ転送する。ラスタ描画の場合は、受け取った
描画命令をラスタデータ処理部１４へ転送するととも
に、ラスタヘッダ内の縦および横の大きさを表す情報を
ディスプレイリスト生成部１２へ転送する。また描画状
態命令については、命令を描画状態記憶部１１４へ転送
する。

【００５１】

【表１】

【００５２】描画状態記憶部１１４は、命令実行部１１
３から受け取った命令に含まれる引数の値で、例えば表
１に示したアンダーラインのない情報についての値の設
定を行い、それらを記憶する。また、ラスタデータ処理
部１４、ディスプレイリスト生成部１２の要求に従っ
て、それらの値を転送する。

【００５３】次に、ラスタデータ処理部１４について説
明する。ラスタデータ処理部１４は、印刷データ解釈部
１１の命令実行部１１３から入力された命令の引数であ
る入力ラスタヘッダと入力ラスタデータとを、描画状態
記憶部１１４から獲得した変換マトリックスを使ってア
フィン変換したり、入力ラスタの色空間を出力装置の色
空間に変換する色空間変換などの処理を行い、出力ラス
タヘッダと出力ラスタデータとを生成してラスタデータ
バッファ１５へ転送する。

【００５４】次に、ディスプレイリスト生成部１２につ
いて詳細に説明する。図９はディスプレイリスト生成部
を示すブロック図である。ディスプレイリスト生成部１
２は、ベクタデータ生成部１２１と、フォント管理部１
２２と、マトリックス変換部１２３と、ショートベクタ
生成部１２４と、リストデータ生成部１２５とから構成
される。

【００５５】ベクタデータ生成部１２１では、印刷デー
タ解釈部１１の命令実行部１１３から送られてきた命令
と引数、描画状態記憶部１１４の値を使用して、塗りつ
ぶし描画を除く、新たに描画するためのベクタデータを
生成する。まず、文字描画の場合について説明する。引
数で与えられた文字コードと描画状態記憶部１１４から
獲得したフォントＩＤとをフォント管理部１２２へ転送
して、文字のアウトラインデータを獲得する。獲得した
アウトラインデータには、描画原点（カレントポイン
ト）の情報が含まれていないので、描画状態記憶部１１
４から獲得したカレントポイントのオフセットをアウト
ラインデータに加えることによって、目的のベクタデー
タを生成する。ラスタ描画の場合には、引数で与えられ
たラスタヘッダの縦および横のサイズからそれに対する
矩形ベクタを生成し、描画状態記憶部１１４から獲得し
たカレントポイントのオフセットを加えることで目的の
ベクタデータを生成する。ストローク描画の場合は、引
数で与えられたベクタと描画状態記憶部１１４から獲得
した各種の線属性とからアウトラインベクタを生成す
る。

【００５６】図１０はアウトラインベクタの説明図であ
る。ストローク描画によって、２本のつながった直線を
描画しようとする場合には、破線で示した中心線の引数
で与えられたベクタと描画状態記憶部１１４から獲得し
た輪郭データの各種の線属性とからアウトラインベクタ
を生成する。すなわち、中心線とその太さと２本の線の
つなぎの処理を指定されることにより、図１０に示すよ
うな太さを持った線の輪郭のアウトラインベクタが生成
される。このように生成したベクタ（塗りつぶし描画の
場合は命令実行部１１３から直接受け取ったベクタ）
を、マトリックス変換部１２３へ転送する。

【００５７】フォント管理部１２２は、各種フォントに
対するアウトラインベクタデータを記憶するとともに、
与えられた文字コードとフォントＩＤとによって、その
文字に対するアウトラインベクタデータを提供する。

【００５８】マトリックス変換部１２３は、ベクタデー
タ生成部１２１から受け取ったベクタデータを、描画状
態記憶部１１４から獲得した変換マトリックスによって
アフィン変換する。このアフィン変換の主な目的は、ア
プリケーションの解像度（座標系）からプリンタの解像
度（座標系）に変換するためのものである。変換マトリ
ックスには下式（１）に示すような３×３のものが使わ
れ、入力ベクタデータ（Ｘｎ，Ｙｎ）は、出力ベクタデ
ータ（Ｘｎ’，Ｙｎ’）に変換されてショートベクタ生
成部１２４へ送られる。

【００５９】

【数１】

【００６０】ショートベクタ生成部１２４は、入力され
たベクタの中に曲線のベクタがある場合にその曲線のベ
クタを、誤差が描画状態記憶部１１４から獲得したｆｌ
ａｔｎｅｓｓ値より小さくなるように、複数のショート
ベクタで近似する処理を行う。これを図１１を参照して
説明する。

【００６１】図１１は曲線の再帰的な分割を示す説明図
である。例えば曲線のベクタには、図１１に黒丸記号で
示した四つの制御点で表現されるベジエ曲線が使われ
る。この場合、ショートベクタ化の処理は、黒丸で示し
た元のベジエ曲線の制御点の間の距離を中点分割してい
き、その分割位置を新たなベジエ曲線の制御点とする。
この制御点は黒四角の記号で示してある。さらに、この
制御点に対してそれらの間を中点分割していくことによ
り、ベジエ曲線をより短い複数のベクタで表現すること
ができる。このように、ベジエ曲線を再帰的に分割し、
分割された制御点で作られる三角の高さ（距離ｄ）がｆ
ｌａｔｎｅｓｓで与えられた値より小さくなった時点で
分割を終了する。そして分割された各ベジエ曲線の始点
と終点を順番に結ぶことにより、ショートベクタ化が完
了する。生成されたショートベクタは、リストデータ生
成部１２５へ送られる。

【００６２】リストデータ生成部１２５は、入力された
ショートベクタデータから、各描画オブジェクト毎に、
ヘッダ部とリスト部とを有したディスプレイリストを生
成する。以下に、オブジェクトが文字／図形の場合とラ
スタの場合とについて、リストデータ生成部１２５で生
成されるディスプレイリストの構造を示す。

【００６３】図１２はリストデータ生成部で生成される
ディスプレイリスト（文字／図形の場合）の構造を示す
図、図１３はリストデータ生成部で生成されるディスプ
レイリスト（ラスタの場合）の構造を示す図である。リ
ストデータ生成部１２５で生成されるディスプレイリス
トは、文字／図形およびラスタデータの場合、ヘッダ部
が異なる。以下にこれら二つの場合のディスプレイリス
トの構造について説明する。

【００６４】図１２に示すように文字／図形の場合、ヘ
ッダ部は、描画オブジェクトの種類を示すＴｙｐｅＩＤ
（この場合、文字あるいは図形描画を示す）と、描画オ
ブジェクトを何色で塗りつぶすかを示す色情報（例え
ば、ＣＭＹＢｋの値等）と、ｙバケットの総数であるｙ
リスト数と、各ｙリストに連結されているセルの総数で
ある連結セル数と、次の描画オブジェクトのディスプレ
イリスト（ＤＬ）へのポインタとから構成される。

【００６５】リスト部は、ｙバケットと、連結セルとか
ら構成される。ｙバケットは、入力された各描画オブジ
ェクト毎のベクタデータの始点のｙ座標値に相当する走
査ラインｙと、最初の連結セルへのポインタであるセル
ポインタからなる。ここで、連結セルの存在しないｙバ
ケットは、リスト部に登録しない。連結セルは、入力さ
れた各描画オブジェクト毎のベクタデータの始点のｘ座
標値と、そのベクタデータの走査ライン当たりのｘの増
分であるΔｘと、そのベクタデータと交差する走査ライ
ンの数であるΔｙと、その走査ラインｙを始点とする異
なるベクタデータが存在するか否かを示す連結フラグか
ら構成される。連結フラグは、次に連結セルが存在する
場合は、フラグ’１’を付加し、最後の連結セルである
場合は、ＥＯＣ（Ｅｎｄ Ｏｆ Ｃｅｌｌ）を表すフラ
グ’０’を付加する。

【００６６】次に、図１３に示すようにラスタデータの
場合、ヘッダ部は、ＴｙｐｅＩＤ（この場合、ラスタ描
画を示す）と、ラスタデータのデータサイズ（１画素当
たりのビット数＊ｗ＊ｈ：ｗは幅、ｈは高さ）と、ラス
タデータの格納されているラスタデータバッファ１５の
アドレスに相当するデータアドレスと、各ｙリストに連
結されているセルの総数である連結セル数と、次の描画
オブジェクトのディスプレイリストへのポインタとから
構成される。リスト部は、上述した文字／図形の場合と
同様であるので説明を省略する。

【００６７】なお、ディスプレイリスト生成部１２で生
成されるディスプレイリストは、ショートベクタ生成部
１２４で生成される各ベクタ同士の繋がり方や、命令実
行部１１３からの描画状態命令にある塗りつぶし方法等
を考慮して生成される。

【００６８】次に、バンド分割部１３について説明す
る。図１４はディスプレイリストのバンド境界での分割
の概要を示す説明図である。バンド分割部１３は、図１
４に示すように、ディスプレイリスト生成部１２で生成
された各描画オブジェクト毎のディスプレイリストの
内、複数のバンドにまたがるディスプレイリストを各バ
ンドに分割する機能を有するもので、バンド毎に分割さ
れたディスプレイリストはディスプレイリストバッファ
部１６へ転送される。図１４においては、第１ベクタに
相当するリスト部が、バンド境界により２分割され、第
２バンドの先頭に新たに連結セルが作られて追加され
る。なお、ｙ_borderは交差しているバンド境界の走査ラ
イン数を示している。次に、第１ベクタを分割する際の
処理の流れについて説明する。

【００６９】図１５はディスプレイリストのバンド分割
の処理の流れを示すフローチャートである。まず、走査
ラインｙ₁ を始点とする第１ベクタに相当するｙ₁ バケ
ットがバンド境界と交わり、複数のバンドにまたがるか
どうかを判定する（ステップＳ２１）。もし、ｙ₁ バケ
ットがバンド境界と交わるならば、Δｙ₁ をΔｙ₁'に更
新する（ステップＳ２２）。次に、第１ベクタに相当す
るディスプレイリストのリスト部を分割し、連結セルを
更新する（ステップＳ２３）。連結セルの更新は、下式
（２）により行う。

【００７０】

【数２】 ｘ＝ｘ₁＋Δｘ₁×Δｙ₁' ……（２ａ） Δｘ＝Δｘ₁ ……（２ｂ） Δｙ＝Δｙ₁−Δｙ₁' ……（２ｃ） 次に、ステップＳ２３での処理が済んだとき、またはス
テップＳ２１の判定でバンド境界との交わりがないとき
には、現在更新した連結セルの連結フラグに従って、連
結フラグがＥＯＣを表すフラグ’０’であるかどうかを
判定する（ステップＳ２４）。ここで、連結フラグが’
０’でなければ、ステップＳ２１に処理を戻し、連結フ
ラグが’０’であれば、リスト終了かどうかを判定する
（ステップＳ２５）。リスト部の他のｙバケットについ
ても、まだバンド境界と交わるベクタがある場合は、ス
テップＳ２１からステップＳ２４までの処理を行い、リ
スト部中のすべてのｙバケットが終了した場合は、リス
ト部が分割された場合のヘッダ部の追加およびヘッダ部
の更新を行い（ステップＳ２６）、バンド分割処理を終
了する。ヘッダ部の追加は、新たにバンド分割されたデ
ィスプレイリストに、現在の描画オブジェクトのヘッダ
部をコピーする。ヘッダ部の更新は、文字／図形の場合
は、ｙリスト数、連結セル数の変更およびディスプレイ
リスト（ＤＬ）のポインタの付け替えを行い、ラスタの
場合は、データサイズ、データアドレスの更新、連結セ
ル数の変更およびＤＬのポインタの付け替えをそれぞれ
行うことになる。

【００７１】以上のように、バンド分割部１３では、各
描画オブジェクト毎のディスプレイリストの全連結セル
に対してステップＳ２１からステップＳ２６までの処理
を行い、バンド単位のディスプレイリストを生成する。

【００７２】次に、ディスプレイリストバッファ１６に
ついて説明する。図１６はディスプレイリストバッファ
におけるディスプレイリストの記憶形態を示す説明図で
ある。ディスプレイリストバッファ１６は、図１６に示
すように、描画オブジェクト毎に、ディスプレイリスト
生成部１２で生成あるいはバンド分割部１３で分割され
たディスプレイリストをバンド単位に記憶するものであ
る。例えば、バンドｉにｎ個の描画オブジェクト含む場
合には、ディスプレイリストバッファ１６のバンドｉに
対応する記憶領域にｎ個のディスプレイリストが記憶さ
れ、これらのディスプレイリストは、バンド毎にディス
プレイリストバンドバッファ１７へ転送される。

【００７３】次に、ディスプレイリスト管理部１８およ
び座標点生成部１９を実装する座標点生成ＬＳＩ５５に
ついて詳細に説明する。図１７は座標点生成ＬＳＩの構
成を示すブロック図である。図１７において、座標点生
成ＬＳＩ５５は、管理回路５５１と、四つの座標点生成
回路５５２Ａ〜５５２Ｄとから構成される。また、座標
点生成ＬＳＩ５５は、内部バス６１に接続されているメ
モリコントローラ５３を介してメモリ５４にアクセスす
る構成になっている。メモリ５４はその一部がディスプ
レイリストバンドバッファ５４１およびエッジリストバ
ッファ５４２に割り当てられている。

【００７４】管理回路５５１は、以下の表２に示す複数
の内部レジスタを有し、現在処理中の走査ライン情報の
管理、ディスプレイリストバンドバッファ５４１および
エッジリストバッファ５４２へのアクセスの制御、ディ
スプレイリストデータのデコード処理、座標点生成回路
５５２の状態管理などの機能を備えるものである。

【００７５】

【表２】

【００７６】座標点生成回路５５２Ａ〜５５２Ｄは、管
理回路５５１から１組ずつセルデータを入力し、走査ラ
イン毎に同期して最大４点のエッジデータを並列に生成
する機能を備えるものである。四つの座標点生成回路５
５２Ａ〜５５２Ｄは、すべて同一の構造を持つ。次に、
座標点生成回路５５２Ａ〜５５２Ｄの具体的な回路構成
について説明するが、これらの構造がすべて同一なた
め、ここでは、座標点生成回路５５２Ａで説明する。

【００７７】図１８は座標点生成回路の回路構成を示す
ブロック図である。座標点生成回路５５２Ａは、ｘ座標
値を保持するＸレジスタ５５２０と、エッジの傾きを保
持するΔＸレジスタ５５２１と、交差数を保持するΔＹ
レジスタ５５２２と、Ｘレジスタ５５２０およびΔＸレ
ジスタ５５２１の値を加算する加算器５５２３と、ΔＹ
レジスタ５５２２の値をデクリメントする演算器５５２
４と、二つのマルチプレクサ５５２５および５５２６
と、実数値を整数値へ変換する演算器５５２７と、ΔＹ
レジスタ５５２２の値を’０’と比較する比較器５５２
８とから構成される。

【００７８】入力Ｘ，ΔＸ，ΔＹは、対応する各レジス
タの初期値であり、管理回路５５１から入力される。入
力ＸＳＥＬ，ΔＹＳＥＬは、それぞれマルチプレクサ５
５２５および５５２６の出力値の切り替え制御信号、入
力ＸＬＤ，ΔＸＬＤ，ΔＹＬＤは、レジスタ５５２０〜
５５２２の書き込み制御信号であり、管理回路５５１か
ら入力される。出力ＣＵＲＸは、管理回路５５１のカレ
ントｘレジスタＣＵＲＸへ出力される。出力ＥＮＤは、
エッジの終了を管理回路５５１に通知するための制御信
号である。また、この例では、傾き情報ΔＸは浮動小数
点データになるので、加算器５５２３の出力は演算器５
５２７にて整数値に変換されている。

【００７９】この座標点生成回路５５２Ａによれば、上
半分の回路にて、アクティブエッジリストのｘとΔｘと
の加算処理を行い、下半分の回路ではアクティブエッジ
リストのΔｙの減算処理を行っている。いずれも、加算
および減算の結果をマルチプレクサ５５２５および５５
２６に戻して、加算および減算を順次行うようにしてい
る。

【００８０】次に、メモリ５４に割り当てられたエッジ
リストバッファ５４２の中の構成およびエッジリストの
データ形式について説明する。図１９はエッジリストバ
ッファの構成を示す図である。エッジリストデータは、
オブジェクトの色情報と最初に現れるエッジのｙ座標値
ｙ_start とから成るヘッダ部と、エッジと各走査ライン
との交点の座標値を含むエッジリスト部とから構成され
る。エッジリストバッファ５４２は、エッジリストデー
タのヘッダ部を格納する領域と、エッジリスト部を格納
する領域とから構成される。エッジリストバッファ５４
２のヘッダ部格納領域の先頭アドレスｅｌｈｄａｄｒ
と、エッジリスト部格納領域の先頭アドレスｙａｄｒ₀
は、座標点生成ＬＳＩ５５の起動時に管理回路５５１の
ＥＬヘッダアドレスレジスタＥＬＨＤＡＤＲおよびＥＬ
トップアドレスレジスタＥＬＴＯＰＡＤＲにそれぞれ書
き込まれる。エッジリストバッファ５４２のエッジリス
ト部格納領域は、１バンドのすべての走査ラインに対し
てそれぞれＭ個のｘ座標値を格納することができる。各
走査ラインのエッジリストの先頭には、そのラインにい
くつのｘ座標値が格納されているかを表すエッジデータ
数Ｐｉが格納される。したがって、各走査ラインにオブ
ジェクトがなければ、エッジデータ数は’０’となり、
エッジリストデータを処理するときには、エッジデータ
数が０であるところは読み飛ばしてオブジェクトのある
エッジリストバッファアドレスのところから処理が開始
される。１走査ラインに格納可能なｘ座標値の最大数Ｍ
の値は、２５６以上の２のべき乗数が望ましい。

【００８１】次に図２０〜２３を用いて、上述したよう
に構成される座標点生成ＬＳＩ５５における、１オブジ
ェクトの座標点生成処理の流れを説明する。図２０は座
標点生成ＬＳＩにおける１オブジェクトの座標点生成処
理の流れを示すフローチャートである。座標点生成ＬＳ
Ｉ５５は、ＣＰＵ５０から座標点生成処理開始の通知を
受け取ると、ディスプレイリストデータのヘッダ部の処
理を開始する（ステップＳ３１）。すなわち、まず、管
理回路５５１がメモリコントローラ５３へディスプレイ
リストバンドバッファ５４１へのリードアクセス要求を
出す。アクセスが許可されると、管理回路５５１はＤＬ
ヘッダアドレスレジスタＤＬＨＤＡＤＲに保持している
アドレスをメモリコントローラ５３へ出力し、そのアド
レスからヘッダ部のデータを読み出して、一旦フェッチ
レジスタＦＥＴＣＨに格納する。また、次のステップＳ
３２の処理に備えて、ＤＬヘッダアドレスレジスタＤＬ
ＨＤＡＤＲに保持しているアドレスとヘッダサイズとか
らディスプレイリストバンドバッファ５４１のｙリスト
部の先頭アドレスを算出し、その値をｙリストアドレス
レジスタＹＬＩＳＴＡＤＲにセットする。

【００８２】オブジェクトが文字または図形の場合に
は、フェッチレジスタＦＥＴＣＨ内のヘッダ情報が、色
情報とセル数と次ヘッダ部アドレスにデコードされて、
それぞれカラーレジスタＣＯＬＯＲ、セルカウンタレジ
スタＮＵＭＣＥＬＬ、ＤＬヘッダアドレスレジスタＤＬ
ＨＤＡＤＲに格納される。

【００８３】オブジェクトがラスタの場合には、フェッ
チレジスタＦＥＴＣＨ内のヘッダ情報が、ラスタデータ
バッファアドレスとラスタデータサイズとセル数と次ヘ
ッダ部アドレスにデコードされる。管理回路５５１は、
デコードしたラスタデータバッファアドレスとラスタデ
ータサイズを印刷画像データ変換ＬＳＩ５６に出力し、
該ラスタデータをホストコンピュータ３０のラスタデー
タバッファ１５からラスタデータバンドバッファメモリ
５８へ転送するよう指示する。デコードしたセル数と次
ヘッダ部アドレスは、それぞれセルカウンタレジスタＮ
ＵＭＣＥＬＬ、ＤＬヘッダアドレスレジスタＤＬＨＤＡ
ＤＲに格納する。

【００８４】ステップＳ３１でバンドの終了が検出され
た場合（ＮＵＭＣＥＬＬ＝０の場合）は、以降の処理を
中断してバンドの終了をＣＰＵ５０に通知し、次のバン
ドの処理に備えてＤＬヘッダアドレスレジスタＤＬＨＤ
ＡＤＲをリセットして、座標点生成ＬＳＩ５５はアイド
ル状態になる。

【００８５】次に、ｙリストの読み込みとデコードを行
うｙリストの処理を行う（ステップＳ３２）。まず、管
理回路５５１がメモリコントローラ５３へディスプレイ
リストバンドバッファ５４１へのリードアクセス要求を
出す。アクセスが許可されると、管理回路５５１はｙリ
ストアドレスレジスタＹＬＩＳＴＡＤＲに保持している
アドレスをメモリコントローラ５３へ出力し、そのアド
レスからｙバケットデータを読み出して、一旦フェッチ
レジスタＦＥＴＣＨに格納する。続いて、フェッチレジ
スタＦＥＴＣＨ内のｙバケットデータは、ｙバケットレ
ジスタＹＢＵＣＫＥＴにコピーされ、ｙリストアドレス
レジスタＹＬＩＳＴＡＤＲがインクリメントされる。最
初のｙバケットを読み込んだ時のみ、そのｙ座標値がス
タートｙレジスタＳＴＡＲＴＹに格納される。

【００８６】次に、セルの読み込みとデコードを行い、
座標点生成回路５５２の内部レジスタを初期設定する
（ステップＳ３３）。ここで、このステップＳ３３の処
理の流れを、図２１を用いて詳細に説明する。

【００８７】図２１はセルの入力とレジスタ設定処理の
流れを示すフローチャートである。まず、セルの読み込
みを行う（ステップＳ４１）。つまり、管理回路５５１
がメモリコントローラ５３へディスプレイリストバンド
バッファ５４１へのリードアクセス要求を出し、アクセ
スが許可されると、管理回路５５１はｙバケットレジス
タＹＢＵＣＫＥＴのセルポインタ部に保持しているアド
レスをメモリコントローラ５３へ出力し、そのアドレス
からセルデータを読み出して、一旦フェッチレジスタＦ
ＥＴＣＨに格納する。

【００８８】次に、フェッチレジスタＦＥＴＣＨ内のセ
ルデータをデコードして、待機状態の座標点生成回路５
５２の内部レジスタにセットする（ステップＳ４２）。
まず、ステータスレジスタＳＴＡＴＵＳの値をチェック
し、待機状態の座標点生成回路５５２を検出する。次
に、検出された座標点生成回路５５２にセルデータから
デコードしたｘ座標値とエッジの傾きΔｘと交差数Δｙ
とを入力し、それぞれＸレジスタ５５２０、ΔＸレジス
タ５５２１、ΔＹレジスタ５５２２へ格納する。ステー
タスレジスタＳＴＡＴＵＳの上記検出された座標点生成
回路５５２の待機状態を表すビットは、処理中を表す’
０’に変更され、アイドルカウンタレジスタＮＵＭＩＤ
ＬＥはデクリメントされる。セルデータからデコードさ
れたｘ座標値は、始点を出力するためにカレントｘレジ
スタＣＵＲＸにもコピーされる。次に、セルデータの連
結フラグ部をデコードし、その値が継続を表す’１’な
らばｙバケットレジスタＹＢＵＣＫＥＴのセルポインタ
部をインクリメントし、連結フラグの値が’０’（ＥＯ
Ｃ）ならばｙバケットレジスタＹＢＵＣＫＥＴのセルポ
インタ部にｎｕｌｌ値をセットする。さらに、セルカウ
ンタレジスタＮＵＭＣＥＬＬをデクリメントし、カレン
トｙレジスタＣＵＲＹにｙバケットレジスタＹＢＵＣＫ
ＥＴに格納しているｙ座標値をコピーする。

【００８９】次に、現在処理しているｙバケットにセル
リストが連結されているか否かを調べてセルポインタ部
の値がｎｕｌｌかどうかが判定される（ステップＳ４
３）。もし、ｙバケットレジスタＹＢＵＣＫＥＴのセル
ポインタ部の値がｎｕｌｌならば、現在処理しているｙ
バケットにはセルが連結されていないので、図２０のセ
ルの入力とレジスタ設定処理のステップＳ３３を終了す
る。ｎｕｌｌでない場合は、セルリストが連結されてい
るので、再びセルを入力するかどうかを決定するため、
アイドルカウンタレジスタＮＵＭＩＤＬＥの値をチェッ
クして、待機状態の座標点生成回路５５２の有無を調べ
る（ステップＳ４４）。ＮＵＭＩＤＬＥ＝０の場合は、
すべての座標点生成回路５５２が処理状態にあるので、
図２０のステップＳ３３の処理を終了する。ＮＵＭＩＤ
ＬＥ＞０の場合は、待機状態の座標点生成回路５５２が
存在するので、ステップＳ４１に戻って、次のセルデー
タを読み込み、ステップＳ４２以下の処理を繰り返す。

【００９０】図２０に戻って、ステップＳ３３で座標点
生成回路５５２にセルデータが設定されると、次のステ
ップＳ３４で実際に座標点の生成と出力が行われる。こ
こで、ステップＳ３４の処理の流れを図２２を用いて詳
細に説明する。

【００９１】図２２は座標点生成と出力処理の流れを示
すフローチャートである。まず、エッジの始点の座標値
をエッジリストバッファ５４２へ出力する（ステップＳ
５１）。このステップＳ５１の処理の詳細は、追って説
明する。続いて、次の走査ラインとエッジの交点の座標
値を計算する（ステップＳ５２）。まず、カレントｙレ
ジスタＣＵＲＹの値がインクリメントされる。次に、処
理状態にある座標点生成回路５５２のＸレジスタ５５２
０およびΔＹレジスタ５５２２の値が、以下に示す式
（３）および式（４）に従って並列に更新される。

【００９２】

【数３】Ｘ＝Ｘ＋ΔＸ ……（３）

【００９３】

【数４】ΔＹ＝ΔＹ−１ ……（４） 最後に、更新されたＸレジスタ５５２０の値が、演算器
５５２７によって整数化されてカレントｘレジスタＣＵ
ＲＸへ格納される。カレントｘレジスタＣＵＲＸは、最
大で四つの座標点を格納できる大きさを持ち、必ず左詰
めで、最小有効ビット（ＬＳＢ）側から有効なデータが
格納されるように管理されている。

【００９４】次に、ステップＳ５２で計算された座標値
をエッジリストバッファ５４２へ出力する（ステップＳ
５３）。このステップＳ５３の処理の詳細は、追って説
明する。次に、エッジの終点を出力した座標点生成回路
５５２を検出して、待機状態にする処理を行う（ステッ
プＳ５４）。エッジの終点を出力し、ΔＹレジスタ５５
２２の値が’０’になった座標点生成回路５５２は、Ｅ
ＮＤ＝’１’を出力する。管理回路５５１では、アクテ
ィブになったＥＮＤ信号を検出し、ステータスレジスタ
ＳＴＡＴＵＳの該当する座標点生成回路５５２の状態を
表すビットを、待機中を表す’１’に変更する。またア
イドルカウンタレジスタＮＵＭＩＤＬＥに、検出された
座標点生成回路５５２の個数を加算する。

【００９５】そして、すべての座標点生成回路５５２が
待機中か否かを調べる（ステップＳ５５）。ここで、ア
イドルカウンタレジスタＮＵＭＩＤＬＥの値が４に等し
ければ、座標点生成回路５５２Ａ〜５５２Ｄはすべて待
機状態にあるので、図２０のステップＳ３４を終了す
る。もし、ＮＵＭＩＤＬＥ＜４ならば、処理中の座標点
生成回路５５２が存在するので、ステップＳ５２に戻
り、次の走査ラインの座標点生成と出力を繰り返す。

【００９６】ここで、ステップＳ５１およびステップＳ
５３における座標点出力処理の流れを図２３を用いて、
詳細に説明する。図２３は座標点出力処理の流れを示す
フローチャートである。まず、管理回路５５１は、メモ
リコントローラ５３へエッジリストバッファ５４２への
アクセス要求を出し、並行してアクセス先のアドレスを
計算する（ステップＳ６１）。現在処理中の走査ライン
に対応するエッジデータ数が格納されているエッジリス
トバッファアドレスは、カレントｙレジスタＣＵＲＹの
値を用いて、

【００９７】

【数５】 ＥＬＴＯＰＡＤＲ＋Ｂ＊Ｍ＊ＣＵＲＹ ……（５） により計算され、エッジリストバッファアドレスレジス
タＥＬＢＡＤＲに格納される。式（５）において、ＥＬ
ＴＯＰＡＤＲはエッジリストバッファ５４２のエッジリ
スト部の先頭アドレスが格納されているＥＬトップアド
レスレジスタＥＬＴＯＰＡＤＲの値を表し、Ｂは一つの
ｘ座標値を表現するために必要なバイト数を表す。Ｂと
Ｍが共に２のべき乗数である場合は、式（５）はハード
ウェアにより１クロックサイクルで計算される。

【００９８】次に、メモリコントローラ５３によりエッ
ジリストバッファ５４２へのアクセスが許可されると、
管理回路５５１はステップＳ６１で計算したアドレスを
メモリコントローラ５３へ出力し、そのアドレスからエ
ッジデータ数を読み込んで、一旦フェッチレジスタＦＥ
ＴＣＨに格納する（ステップＳ６２）。

【００９９】次に、フェッチレジスタＦＥＴＣＨ内のエ
ッジデータ数に（４−ＮＵＭＩＤＬＥ）の値を加算し、
結果をエッジリストバッファ５４２の読み込んだ時と同
一のアドレスへ書き込む（ステップＳ６３）。

【０１００】最後に、まず、エッジリストバッファアド
レスレジスタＥＬＢＡＤＲに、フェッチレジスタＦＥＴ
ＣＨ内のエッジデータ数にＢを乗じた値を加え、続い
て、このアドレスへカレントｘレジスタＣＵＲＸの値を
書き込む（ステップＳ６４）。以上でステップＳ５１ま
たはステップＳ５３の座標点出力の処理は終了する。

【０１０１】図２０に戻って、ステップＳ３４の処理が
終了すると、次に、セルカウンタレジスタＮＵＭＣＥＬ
Ｌの値がチェックされる（ステップＳ３５）。ここで、
ＮＵＭＣＥＬＬ＞０ならば、ｙバケットレジスタＹＢＵ
ＣＫＥＴに格納されているセルポインタの値がチェック
される（ステップＳ３６）。もし、セルポインタの値が
ｎｕｌｌならばステップＳ３２へ戻り、ｎｕｌｌ以外な
らばステップＳ３３へ戻る。ステップＳ３５において、
ＮＵＭＣＥＬＬ＝０ならば、オブジェクトのヘッダ情報
をエッジリストバッファ５４２へ書き込み、一連の座標
点生成処理を終了する（ステップＳ３７）。まず、管理
回路５５１がメモリコントローラ５３へエッジリストバ
ッファ５４２へのライトアクセス要求を出す。アクセス
が許可されると、管理回路５５１はエッジリストヘッダ
アドレスレジスタＥＬＨＤＡＤＲに保持しているアドレ
スをメモリコントローラ５３へ出力し、そのアドレスに
カラーレジスタＣＯＬＯＲおよびスタートｙレジスタＳ
ＴＡＲＴＹの値を書き込む。次に、１オブジェクト分の
座標点生成処理が終了したことをＣＰＵ５０に通知し
て、座標点生成ＬＳＩ５５はアイドル状態になる。

【０１０２】次に、図２に示したソート部２０について
詳細に説明する。まず、ソート部２０における処理の流
れの概要を図２４を参照して説明する。図２４はソート
部における処理の流れを示すフローチャートである。ソ
ート部２０において、まず、エッジリストバッファ２１
のアドレスｅｌｈｄａｄｒに格納されているヘッダ情報
を読み込む（ステップＳ７１）。次に、ヘッダ情報中の
ｙ_start の値により、最初に読み込むエッジリストバッ
ファアドレスｙ_adr を設定する（ステップＳ７２）。そ
して、エッジリストバッファアドレスｙ_adr から、エッ
ジデータ数Ｐi を読み込む（ステップＳ７３）。

【０１０３】ここで、読み込んだエッジデータ数Ｐi が
０か否かを判定する（ステップＳ７４）。０の場合は、
現在のエッジリストバッファアドレスｙ_adr が示すバッ
ファも含めて、それ以降のエッジリストバッファ中に
は、エッジデータは存在しないので、ソート処理を終了
する。エッジデータ数Ｐi が０でない場合は、エッジデ
ータが存在するので、その読み込んだエッジデータ数Ｐ
i と設定値との大小判定を行う（ステップＳ７５）。こ
こでは、設定値＝１としてある。エッジデータ数Ｐi と
設定値との比較の結果、エッジデータ数が設定値より大
きい場合は、現在のエッジリストバッファアドレスｙ
_adr が示すバッファ中のエッジデータのソートが必要と
判定され、現在のエッジリストバッファアドレスｙ_adr
が示すバッファ中に存在するエッジデータを、ｘ座標の
値の小さい順にソートする（ステップＳ７６）。ソート
が終了すると、あるいはステップＳ７５の判定にて、エ
ッジデータ数Ｐi が設定値以下で、現在のエッジリスト
バッファアドレスｙ_adr が示すバッファ中のエッジデー
タのソートは必要ないと判定された場合には、エッジリ
ストバッファアドレスｙ_adr を次の走査ラインに対応す
るアドレスに設定する（ステップＳ７７）。そして、ア
ドレスがエッジリストバッファ領域を超えたかどうかを
判定する（ステップＳ７８）。ここで、アドレスがエッ
ジリストバッファ領域を超えていない場合は、ステップ
Ｓ７３に処理を移して繰り返しソート処理を行う。も
し、アドレスがエッジリストバッファ領域を超えた場合
には、ソート処理を終了する。

【０１０４】以上がソート部２０における処理の流れの
概要である。次に、ステップＳ７６のエッジデータのソ
ート方法について詳細に説明する。図２５はソート部に
おけるソート方法を示す説明図である。入力されたｎ個
のエッジデータは（Ａ）で示してある。このｎ個のエッ
ジデータのうち、まず、真ん中に位置するｎ／２番目の
エッジデータ値ｘに着目する。次に、全エッジデータに
対して、（Ｂ）に示したように、エッジデータ値ｘより
も小さいか否かにより、それぞれのエッジデータをエッ
ジデータ値ｘ以下（１〜ｉ）のものと、エッジデータ値
ｘ以上（ｊ〜ｎ）であるものとに振り分ける。今度は、
（Ｃ）に示したように、１〜ｉまでのエッジデータおよ
びｊ〜ｎまでのエッジデータそれぞれに対して、上記で
述べた方法で振り分ける。これを、すべてのエッジデー
タが値の小さい順にソートされるまで再帰的に繰り返
す。これにより、（Ｄ）に示したように、順不同で入力
されたエッジデータはソートされることになる。次に、
ソート部２０でこのソート方法を実現するソフトウェア
の機能構成について説明する。

【０１０５】図２６はソート部の構成例を示すブロック
図である。ソート部２０は、エッジデータ入力部２０１
と、ソートバッファ２０２と、エッジデータ出力部２０
３と、ソート処理管理部２０４と、中点値選択部２０５
と、エッジデータ判定部２０６と、エッジデータ分別部
２０７とから構成される。

【０１０６】エッジデータ入力部２０１はエッジリスト
バッファ２１からエッジデータが入力され、入力された
エッジデータはソートバッファ２０２に一時的に蓄えら
れる。エッジデータ出力部２０３はソートバッファ２０
２内の最終的にソートされたエッジデータをエッジリス
トバッファ２１へ出力する。ソート処理管理部２０４は
ソートすべきエッジデータ数の設定などのソート処理全
体を管理する。中点値選択部２０５はソートバッファ２
０２内のエッジデータに対して（エッジデータ数／２）
番目の値を選択する。エッジデータ判定部２０６は（エ
ッジデータ数／２）番目の値とエッジデータ値との大小
比較を行い、エッジデータ分別部２０７はエッジデータ
判定部２０６の比較結果に従い、エッジデータを振り分
ける機能を有する。

【０１０７】次に、上述したように構成されるソート部
２０におけるソート処理の流れを図２７のフローチャー
トを用いて詳細に説明する。図２７はソート部の処理の
流れを示すフローチャートである。エッジデータ入力部
２０１に入力されたエッジデータは、まず、ソートバッ
ファ２０２に蓄えられる。ここで、ソート処理管理部２
０４により、エッジデータの個数ｎが算出される。ただ
し、１回目のソート処理の場合は、エッジリストバッフ
ァ２１中のエッジデータ（ＥＤ）の数の値はｎと設定す
る。また、ｆｉｒｓｔ値ｉ＝１、ｌａｓｔ値ｊ＝ｎも設
定する（ステップＳ８１）。次に、中点値選択部２０５
により、エッジデータの（ｎ／２）番目の値ｘを選択す
る（ステップＳ８２）。

【０１０８】次に、エッジデータ判定部２０６にて、ソ
ートバッファ２０２の中の値ｘとｉ番目のエッジデータ
の値との比較を行い（ステップＳ８３）、値ｘが大きけ
れば、ｉをインクリメントする（ステップＳ８４）。ｉ
をインクリメントしていって、値ｘが大きくなくなれ
ば、次に、ソートバッファ２０２の中の値ｘとｊ番目の
エッジデータの値との比較を行い（ステップＳ８５）、
値ｘが小さければ、ｊをデクリメントする（ステップＳ
８６）。ｊをデクリメントしていって、値ｘが小さくな
れば、エッジデータ判定部２０６で振り分けが必要と判
定されたエッジデータに対して、エッジデータ分別部２
０７により、エッジデータの振り分けを行い、振り分け
た結果をソートバッファ２０２に出力する（ステップＳ
８７）。

【０１０９】次に、ソート処理管理部２０４にて、ｉと
ｊとを比較し、ソートバッファ２０２の中の全エッジデ
ータに対して、値ｘとの大小比較が完了したかどうかを
判定する（ステップＳ８８）。ここで、完了していない
場合は、ステップＳ８３からステップＳ８７の処理を繰
り返す。値ｘとの大小比較がすべて完了している場合に
は、ソート処理管理部２０４により、ｉが１より大きい
かどうかを判定し（ステップＳ８９）、ｉがまだ１より
大きい場合には値ｘにより振り分けられた１〜ｉまでの
エッジデータに対して、ステップＳ８１からステップＳ
８８までの処理を繰り返し行うようにする。ｉが１の場
合には、ソート処理管理部２０４により、ｊがｎより小
さいかどうかを判定し（ステップＳ９０）、ｊがまだｎ
より小さい場合には値ｘにより振り分けられたｊ〜ｎま
でのエッジデータに対して、ステップＳ８１からステッ
プＳ８９までの処理を繰り返し行うようにする。これに
より、すべてのエッジデータがｘの値の小さい順にソー
トされることになる。

【０１１０】上記の処理がすべて終了し、ソートバッフ
ァ２０２中の全エッジデータがソートされると、エッジ
データ出力部２０３は、エッジリストバッファ２１にソ
ートバッファ２０２中のエッジデータを出力する。

【０１１１】次に、印刷画像データ変換部２２を実装す
る印刷画像データ変換ＬＳＩ５６について詳細に説明す
る。図２８は印刷画像データ変換ＬＳＩの構成を示すブ
ロック図である。図２８において、印刷画像データ変換
ＬＳＩ５６は、エッジリスト入力回路５６１と、データ
演算回路５６２と、アドレス計算回路５６３と、メモリ
描画回路５６４と、ラスタデータ転送回路５６５とから
構成される。また、印刷画像データ変換ＬＳＩ５６は、
メモリ５４内のエッジリストバッファ５４２にはカード
内部バス６１に接続されているメモリコントローラ５３
を介してアクセスし、出力バッファ５７およびラスタデ
ータバンドバッファ５８にはローカルバスを用いて直接
アクセスする構成になっている。この構成により、出力
バッファ５７あるいはラスタデータバンドバッファ５８
との高速なデータ転送を実現している。

【０１１２】エッジリスト入力回路５６１は、エッジリ
ストバッファ５４２からエッジリストデータを読み込
み、オブジェクトのヘッダ情報あるいは描画する線分の
始点および終点の座標値をデコードして、データ演算回
路５６２およびアドレス計算回路５６３へ出力する機能
を備えるものである。

【０１１３】データ演算回路５６２は、描画するオブジ
ェクトが文字または図形の場合にはオブジェクトによっ
て固定的な色を表す色データを入力し、この値を用いて
スクリーン処理を行って、メモリ描画回路５６４へ出力
する機能を備える。描画するオブジェクトがラスタの場
合には、入力されるラスタデータに対してスクリーン処
理を行って、メモリ描画回路５６４へ出力する機能を備
える。

【０１１４】アドレス計算回路５６３は、描画する線分
の始点および終点の座標値を入力して、始点に対応する
出力バッファアドレスと描画する線分のワード長とを計
算して、メモリ描画回路５６４へ出力するものである。

【０１１５】メモリ描画回路５６４は、入力されたアド
レスと描画データとを用いて、描画する線分を表すすべ
てのワードにデータが書き込まれるまで、出力バッファ
５７への描画処理を繰り返し行う機能を備えるものであ
る。

【０１１６】ラスタデータ転送回路５６５は、描画する
オブジェクトがラスタの場合に、座標点生成ＬＳＩ５５
から通知を受けて、描画する１バンド分のラスタデータ
を、ホストコンピュータ３０にラスタデータバッファ１
５として使用されるＤＲＡＭ３３からラスタデータバン
ドバッファ５８へ転送する機能を備える。また、ラスタ
データをラスタデータバンドバッファ５８から読み出し
てデータ演算回路５６２へ出力する機能を備える。

【０１１７】次に、上述したように構成される印刷画像
データ変換ＬＳＩ５６における、描画処理の流れについ
て説明する。印刷画像データ変換ＬＳＩ５６は、描画処
理カード３８のＣＰＵ５０から１オブジェクトの描画処
理開始の通知を受け取ると、まずエッジリスト入力回路
５６１がエッジリストバッファ５４２からエッジリスト
のヘッダ部を読み込んで、オブジェクトの色情報と最初
のｙ座標値とにデコードし、内部レジスタに格納する。
次に、式（５）に従って最初のｙ座標値に対応するエッ
ジリストバッファアドレスが計算され、そのアドレスか
らエッジデータ数Ｐ_i を読み込んで内部レジスタに格納
する。その後、座標点データを二つずつ読み込んで出力
バッファ５７へ描画するという処理を繰り返す。座標点
データを二つずつ読み込む度に、エッジデータ数Ｐ_i を
格納しているレジスタを二つずつデクリメントし、その
レジスタの値が０になったら次の走査ラインの処理に移
る。エッジリスト入力回路５６１によってデコードされ
た二つのｘ座標値（ｘ_j ，ｘ_j+1 ）と現在の走査ライン
を表すｙ座標値ｙ_i は、データ演算回路５６２とアドレ
ス計算回路５６３へ出力される。エッジリストヘッダか
らデコードされたオブジェクトの色情報は、データ演算
回路５６２へ出力される。データ演算回路５６２では、
入力された色データと座標値データを用いてスクリーン
処理を行い、１または複数のワード分の描画データを生
成して、メモリ描画回路５６４へ出力する。アドレス計
算回路５６３では、入力された座標値を用いて、次式、

【０１１８】

【数６】 ｓｔａｒｔａｄｒ＋ｘ_j＋ｗｐｓｌ＊ｙ_i ……（６） により、描画する線分の始点（ｘ_j ，ｙ_i ）が格納され
る出力バッファアドレスを計算する。式（６）におい
て、ｓｔａｒｔａｄｒは座標原点（０，０）が格納され
る出力バッファアドレスを表す定数であり、ｗｐｓｌは
１走査ラインを格納するのに必要な出力バッファ５７の
ワード数を表す定数である。またアドレス計算回路５６
３では、入力された二つのｘ座標値（ｘ_j ，ｘ_j+1 ）か
ら、描画する線分のワード長を計算する。計算された始
点アドレスと線分の長さは、メモリ描画回路５６４へ出
力される。メモリ描画回路５６４では、入力された始点
アドレスから順次、入力された描画データを出力バッフ
ァ５７へ書き込む。この時、１ワード描画する毎に線分
の長さを格納したレジスタの値をデクリメントしてい
き、該レジスタの値が０になったら線分の描画を終了す
る。描画するオブジェクトがラスタの場合は、１ワード
毎にラスタデータバンドバッファ５８から描画するデー
タを読み出して、データ演算回路５６２でスクリーン処
理を行い、メモリ描画回路５６４が出力バッファ５７へ
描画する。

【０１１９】以上はエッジデータをオブジェクト毎でし
かもエッジの開始点毎に座標点生成回路に入力し、すべ
ての座標点生成回路での処理が終了したら、次のエッジ
データを処理していくようにしたが、この場合、エッジ
データの数によりすべての座標点生成回路が常に同時に
処理中とは限らないので、待機中の座標点生成回路が発
生してくる。次に、このような座標点生成回路がないよ
うに有効利用した本発明の第２の実施の形態について説
明する。

【０１２０】図２９は第２の実施の形態での座標点生成
ＬＳＩの構成例を示すブロック図である。図２９におい
て、座標点生成ＬＳＩ５５は、管理回路５５１と、四つ
の座標点生成回路５５２Ａ〜５５２Ｄと、部分ソート回
路５５３とから構成されている。さらに、管理回路５５
１にはエッジデータ追加処理回路５５１１が含まれてい
る。また、座標点生成ＬＳＩ５５はカード内部バス６１
に接続されているメモリコントローラ５３を介してメモ
リ５４に割り当てられたディスプレイリストバンドバッ
ファ５４１およびエッジリストバッファ５４２にアクセ
スする構成になっている。

【０１２１】管理回路５５１は、以下の表３に示す複数
の内部レジスタを有し、現在処理中の走査ライン情報の
管理、ディスプレイリストバンドバッファ５４１および
エッジリストバッファ５４２へのアクセス制御、座標点
生成回路５５２の状態管理、エッジデータの追加判定処
理、ディスプレイリストデータのデコードおよび再構成
処理、部分ソート回路５５３で生成されたエッジデータ
の内部レジスタ格納処理といった機能を備えたものであ
る。

【０１２２】

【表３】

【０１２３】座標点生成回路５５２Ａ〜５５２Ｄは、管
理回路５５１から１組ずつセルデータを入力し、走査ラ
イン毎に同期して最大４点のエッジデータを並列に生成
する機能を備えるものである。四つの座標点生成回路５
５２Ａ〜５５２Ｄは、すべて同一の構造を持つ。部分ソ
ート回路５５３は、座標点生成回路５５２で生成された
複数のエッジデータを昇順に並べ換える機能を備えたも
のである。

【０１２４】次に、上述した各部のうち管理回路５５１
中のエッジデータ追加処理回路５５１１、座標点生成回
路５５２、部分ソート回路５５３の構成および動作につ
いて更に詳細に説明する。また、エッジリストバッファ
５４２の構成についても詳細に説明する。

【０１２５】図３０はエッジデータ追加処理回路の構成
例を示すブロック図である。管理回路５５１内に設けら
れたエッジデータ追加処理回路５５１１はプリフェッチ
部５５１１０と比較部５５１１１とから構成される。プ
リフェッチ部５５１１０はｍ個（この例では４個）のｙ
バケットバッファを持ち、座標点生成処理開始前にディ
スプレイリストバンドバッファ５４１より座標点生成処
理を待っているｍ個のｙバケットデータ（ｙ座標値ｙ_i
および先頭セルポインタ＆_i ）がプリフェッチされる。
そして、比較部５５１１１において現走査ラインのｙ座
標値ｙ_currentとプリフェッチ部５５１１０のｙバケッ
トバッファの値を参照して比較し、エッジデータの追加
処理が発生しないかチェックする。プリフェッチデータ
がすべてチェックされた場合は、新たにｍ個のｙバケッ
トデータをプリフェッチするが、その読み込み処理は座
標点データ生成処理中に並行して行われる。また、現走
査ラインのｙ座標値ｙ_current より大きいｙ座標値を持
つｙバケットが現れた場合、そのｙバケットデータをｙ
_next，＆_nextとして比較部５５１１１内部のバッファに
保持しておく。これにより、更新された走査ラインのｙ
座標値がｙ_nextより大きくなるまではこのバッファの値
との比較を行えばよいことになり、処理の効率化を図る
ことができる。次に、座標点生成回路５５２Ａ〜５５２
Ｄの具体的な回路構成について説明するが、これらの構
造がすべて同一なため、ここでは、代表して座標点生成
回路５５２Ａで説明する。

【０１２６】図３１は第２の実施の形態での座標点生成
回路の回路構成を示すブロック図である。各レジスタお
よび演算器を表す５５２０〜５５２８については、図１
８で述べたものと同様なのでここでは説明を省略する。
第２の実施の形態における座標点生成回路５５２Ａは、
実数値を整数値へ変換する演算器５５２７の出力にマル
チプレクサ５５２９が接続されていることを特徴とす
る。マルチプレクサ５５２９は、座標点生成回路５５２
がエッジデータ生成処理をしている場合はエッジのｘ座
標値を出力し、待機中である場合はｘ座標値の取り得る
最大値を出力する。このようにして得られた四つのｘ座
標値は次段の部分ソート回路５５３に出力される。

【０１２７】図３２は部分ソート回路の回路構成を示す
ブロック図である。部分ソート回路５５３は、二つのｘ
座標値を昇順にソートする三つの２入力ソート回路５５
３８〜５５３１０と、ソートするデータを保持する四つ
のレジスタ５５３０〜５５３３と、座標点生成回路５５
２からの入力データと１サイクル目のソートデータとを
管理回路５５１からの選択信号ＳＥＬにより各レジスタ
５５３０〜５５３３へ選択入力するための四つのマルチ
プレクサ５５３４〜５５３７とから構成されている。

【０１２８】まず、座標点生成回路５５２Ａ〜５５２Ｄ
で生成された四つのｘ座標値はマルチプレクサ５５３４
〜５５３７により選択出力されて、各々の対応するレジ
スタ５５３０〜５５３３にその値が書き込まれる。そし
て、第１段目の二つの２入力ソート回路５５３８，５５
３１０はこれらのｘ座標値を二つずつ昇順にソートす
る。次に、２入力ソート回路５５３８の出力データの大
きい方と２入力ソート回路５５３１０の出力データの小
さい方とが第２段目の１つの２入力ソート回路５５３９
に入力され、ここで昇順にソートされる。このようにし
て、２段のソート処理によりソートされた四つのｘ座標
値は先のマルチプレクサ５５３４〜５５３７に入力さ
れ、マルチプレクサ５５３４〜５５３７は切り替えられ
て各々の対応するレジスタ５５３０〜５５３３にソート
処理途中のｘ座標値を書き込む。そして、先のソート処
理と同様に２段のソート処理により各々二つずつ昇順に
ソートを行うことにより、最終的に昇順にソートされた
四つのｘ座標値が得られる。ソート処理が終了した四つ
のｘ座標値は管理回路５５１のカレントｘｉレジスタＣ
ＵＲＸｉ（ｉ＝１〜４）に出力される。

【０１２９】次に、メモリ５４に割り当てられたエッジ
リストバッファ５４２の中の構成およびエッジリストの
データ形式について説明する。図３３は第２の実施の形
態でのエッジリストバッファの構成を示す図である。エ
ッジリストデータは、オブジェクトの色情報と最初に現
れるエッジのｙ座標値ｙ_start とから成るヘッダ部と、
エッジと各走査ラインとの交点の座標値を含むエッジリ
スト部とから構成される。エッジリスト部の各走査ライ
ンのｘ座標値は、部分ソート回路５５３で同時にソート
する数ｎ（ここでは、ｎ＝４）ずつ昇順にソートされて
いる。エッジリストバッファ５４２は、エッジリストデ
ータのヘッダ部を格納する領域と、エッジリスト部を格
納する領域とから構成される。エッジリストバッファ５
４２のヘッダ部格納領域の先頭アドレスｅｌｈｄａｄｒ
と、エッジリスト部格納領域の先頭アドレスｙａｄｒ₀
は、座標点生成ＬＳＩ５５の起動時に管理回路５５１の
ＥＬヘッダアドレスレジスタＥＬＨＤＡＤＲおよびＥＬ
トップアドレスレジスタＥＬＴＯＰＡＤＲにそれぞれ書
き込まれる。エッジリスト部格納領域は、１バンドのす
べての走査ラインに対してＭ個のｘ座標値を格納するこ
とができる。各走査ラインのエッジリストの先頭には、
そのラインにいくつのｘ座標値が格納されているかを表
すエッジデータ数Ｐ_i が格納される。座標点生成ＬＳＩ
５５からは部分ソート回路５５３で同時にソートする数
ｎ（ｎ＝４）ずつｘ座標値を出力するので、エッジデー
タ数Ｐ_i はｎの倍数となる。ここで、待機中の座標点生
成回路からのデータは座標点生成で出力される最大値以
上の値、ここでは最大値を入力しておく。これにより、
ソート部２０でソフトウェアにより行われるｘ座標値の
ソートの際には、これら最大値は走査ラインの最後に整
列されることになる。１走査ラインに格納可能なｘ座標
値の最大数Ｍの値は、２５６以上の２のべき乗数が望ま
しい。

【０１３０】次に、上述したように構成された座標点生
成ＬＳＩ５５における、１描画オブジェクトのディスプ
レイリストからエッジデータを生成するまでの処理の流
れについて、図３４〜図３９を用いて説明する。

【０１３１】図３４は第２の実施の形態での座標点生成
ＬＳＩの全体の処理の流れを示すフローチャートであ
る。座標点生成ＬＳＩ５５は、ＣＰＵ５０からの１描画
オブジェクトに対する座標点生成開始の指示を待ち、ホ
ストコンピュータ３０からディスプレイリストバンドバ
ッファ５４１へのバンド単位のディスプレイリストデー
タの書き込みが終了し、ＣＰＵ５０から座標点生成開始
の指示を受けることによって座標点生成処理を開始す
る。

【０１３２】座標点生成処理では、まず、１描画オブジ
ェクトに対するディスプレイリストデータのヘッダ情報
の読み込み、解釈、属性管理といったディスプレイリス
トヘッダの処理を行う（ステップＳ１０１）。すなわ
ち、管理回路５５１は一つ目の描画オブジェクトに対す
るディスプレイリストデータのヘッダ情報の読み込み要
求をメモリコントローラ５３へ出す。メモリコントロー
ラ５３からアクセス許可信号を受け取ったら、ＤＬヘッ
ダアドレスレジスタＤＬＨＤＡＤＲに保持しているアド
レスを出力して、一つ目の描画オブジェクトに対するデ
ィスプレイリストデータのヘッダ情報の読み込みを行
う。また、この時、ＤＬヘッダアドレスレジスタＤＬＨ
ＤＡＤＲに保持しているアドレスとヘッダサイズからＤ
Ｌバンドバッファのｙリスト部の先頭アドレスとを算出
し、その値をｙリストトップアドレスレジスタＹＬＴＯ
ＰＡＤＲに格納する。読み込まれたヘッダ情報は一旦フ
ェッチレジスタＦＥＴＣＨに格納され、その内容は管理
回路５５１で解釈され、その描画オブジェクトに関する
属性を管理回路５５１内のレジスタ群に格納して以降の
ステップに移る。管理回路５５１では、まず、描画オブ
ジェクトの種類が判別され、描画オブジェクトが文字ま
たは図形の場合には、フェッチレジスタＦＥＴＣＨ内の
ヘッダ情報は、色情報、ｙリスト数、セル数、次ヘッダ
部アドレスにデコードされてそれぞれカラーレジスタＣ
ＯＬＯＲ、トータルｙリストレジスタＮＵＭＬＩＳＴ、
セルカウンタレジスタＮＵＭＣＥＬＬ、ＤＬヘッダアド
レスレジスタＤＬＨＤＡＤＲに格納される。描画オブジ
ェクトがラスタの場合には、フェッチレジスタＦＥＴＣ
Ｈ内のヘッダ情報は、ラスタデータバッファアドレスと
ラスタデータサイズとセル数と次ヘッダ部アドレスとに
デコードされる。管理回路５５１は、デコードしたラス
タデータバッファアドレスとラスタデータサイズとを印
刷画像データ変換ＬＳＩ５６に出力し、そのラスタデー
タをホストコンピュータ３０のラスタデータバッファ１
５からラスタデータバンドバッファ５８へ転送するよう
指示する。デコードしたセル数と次ヘッダ部アドレスと
は、それぞれセルカウンタレジスタＮＵＭＣＥＬＬ、Ｄ
ＬヘッダアドレスレジスタＤＬＨＤＡＤＲに格納する。
なお、描画オブジェクトがラスタの場合のディスプレイ
リストには、ラスタデータが描画される矩形領域情報し
かないため、リスト部のｙバケットは１個で済む。した
がって、ヘッダ情報にはｙリスト数は含まれず、また後
述するセルの追加判定処理も発生しないため、トータル
ｙリストレジスタＮＵＭＬＩＳＴへの書き込みは行われ
ない。また、色情報も不要であるためカラーレジスタＣ
ＯＬＯＲへの書き込みも行われない。

【０１３３】次に、ｙリストの処理を行う（ステップＳ
１０２）。ここでは、ｙバケットの読み込み、読み込ん
だｙバケットに連結されている連結セルの読み込み、セ
ル読み込み後のディスプレイリストの再構成といった処
理を行うが、その処理の詳細については後述する通りで
ある。

【０１３４】次に、セルの処理を行う（ステップＳ１０
３）。ここでは、ステップＳ１０２で読み込んだセルデ
ータから座標点の算出、走査ラインの更新、エッジリス
トバッファ５４２へのエッジデータおよびエッジデータ
数の出力、四つの座標点生成回路の状態管理、セルデー
タの追加、セル追加後のディスプレイリストの再構成と
いった処理を行う。このセルの処理の詳細については後
述する通りである。

【０１３５】次に、描画オブジェクトに含まれるすべて
のセルの処理が終了したかどうかを判別する処理を行う
（ステップＳ１０４）。すなわち、ステップＳ１０１で
セットしたセルカウンタレジスタＮＵＭＣＥＬＬの値を
チェックし、ＮＵＭＣＥＬＬ＞０ならばステップＳ１０
２に移って先述の処理を繰り返し、ＮＵＭＣＥＬＬ＝０
ならば、その描画オブジェクトに対する処理が終了した
ものと判定する。

【０１３６】そして、当該描画オブジェクトの色情報と
エッジリストデータが存在する走査ラインの開始アドレ
スとを含むヘッダ情報をエッジリストバッファ５４２へ
出力し、ＣＰＵ５０にその描画オブジェクトに対する処
理が終了したことを通知して再び待機状態に戻るといっ
た終了処理を行う（ステップＳ１０５）。まず、管理回
路５５１がメモリコントローラ５３へエッジリストバッ
ファ５４２への書き込み要求を出力する。メモリコント
ローラ５３からアクセス許可信号を受け取ったら、ＥＬ
ヘッダアドレスレジスタＥＬＨＤＡＤＲに保持している
アドレスを出力し、次に、カラーレジスタＣＯＬＯＲと
スタートｙレジスタＳＴＡＲＴＹとの値を出力してエッ
ジリストバッファ５４２への書き込みを行う。そして、
ＣＰＵ５０にその描画オブジェクトに対する座標点生成
処理が終了したことを通知して再び待機状態に戻る。

【０１３７】次に、この１オブジェクトに対する座標点
生成処理のステップＳ１０２におけるｙリストの処理の
処理内容についてより詳細に説明する。図３５は第２の
実施の形態での座標点生成ＬＳＩのｙリストの処理の流
れを示すフローチャートである。まず、ｙリストの読み
込みを行う（ステップＳ１１１）。管理回路５５１は、
ｙリストトップアドレスレジスタＹＬＴＯＰＡＤＲの内
容をｙリストアドレスレジスタＹＬＩＳＴＡＤＲに読み
込み、最初のｎ個のｙバケットの読み出し要求をメモリ
コントローラ５３に出す。メモリコントローラ５３から
読み出し許可信号が来たら、ＹＬＩＳＴＡＤＲの値をメ
モリコントローラ５３に出力してｎ個のｙバケットデー
タの連続読み出しを行う。読み出されたデータはプリフ
ェッチレジスタＰＲＥＦＥＴＣＨに格納し、一つ目のｙ
バケットデータを一旦フェッチレジスタＦＥＴＣＨに格
納して、ｙ座標値とエッジセルへのポインタの切り出し
を行い、ｙ座標値をカレントｙレジスタＣＵＲＹとスタ
ートｙレジスタＳＴＡＲＴＹとに、ポインタをセルアド
レスレジスタＣＥＬＬＡＤＲに格納する。さらにｙバケ
ットの読み出し回数をカウントするｙリストカウンタレ
ジスタＹＣＯＵＮＴをインクリメントする。

【０１３８】次に、読み込んだｙバケットにセルがある
か否かを判定する（ステップＳ１１２）。もし、セルア
ドレスレジスタＣＥＬＬＡＤＲの値がｎｕｌｌならば、
ステップＳ１１１に戻り、プリフェッチレジスタＰＲＥ
ＦＥＴＣＨから次のｙバケットデータをフェッチレジス
タＦＥＴＣＨに格納する。セルアドレスレジスタＣＥＬ
ＬＡＤＲの値がｎｕｌｌでなければ、ステップＳ１１３
に移ってその値が指し示すセルのデータ読み出しを行う
（ステップＳ１１３）。なお、ディスプレイリストバン
ドバッファ５４１からのｙリストの読み込みが一巡目の
時は、各ｙバケットには連結セルが必ず存在するため、
ポインタアドレスがｎｕｌｌとなることはない。ポイン
タアドレスがｎｕｌｌとなるのは、後述するセルポイン
タの更新のステップで連結セルがなくなって更新処理が
施された後に、本ステップを迎えた場合である。また、
ステップＳ１１１で最初のｎ個のｙバケットデータをプ
リフェッチした後は、座標点生成処理に並行してｙバケ
ットデータのプリフェッチを行って、プリフェッチレジ
スタＰＲＥＦＥＴＣＨの内容が更新される。

【０１３９】ステップＳ１１３のセルを読み込むステッ
プでは、セルデータの読み出し要求をメモリコントロー
ラ５３に出す。メモリコントローラ５３から読み出し許
可信号が来たら、セルアドレスレジスタＣＥＬＬＡＤＲ
の値をメモリコントローラ５３に出力して一つのセルデ
ータの読み出しを行う。読み出されたデータは一旦フェ
ッチレジスタＦＥＴＣＨに格納して、始点のｘ座標を表
すｘ座標値、ｘ座標値の増分Δｘ、エッジと交差する走
査ライン数を表すΔｙの値、および次のセルへの継続状
態を示す連結フラグをそれぞれ切り出し、待機中の座標
点生成回路５５２Ａ〜５５２Ｄに連結フラグ以外の各デ
ータを転送して、ｘ座標値をＸレジスタに、ΔｘをΔＸ
レジスタに、ΔｙをΔＹレジスタにそれぞれ格納して次
のステップＳ１１４に移る。なお、この時、データが転
送された座標点生成回路５５２Ａ〜５５２Ｄから出力さ
れるＥＮＤ信号は’０’となり、ステータスレジスタＳ
ＴＡＴＵＳのその座標点生成回路５５２Ａ〜５５２Ｄに
対応するビットにも’０’が書き込まれて、当該座標点
生成回路５５２Ａ〜５５２Ｄは待機状態ではなくなった
ことを示す。データ転送後、座標点生成回路５５２Ａ〜
５５２Ｄは、現在処理中の走査ラインに対するエッジの
座標点を生成してその値を部分ソート回路５５３に出力
し、部分ソート回路５５３によってソートされた各座標
点データを管理回路５５１のエッジデータレジスタＣＵ
ＲＸｉ（ｉ＝１〜４）に格納する。

【０１４０】次に、セルポインタの更新処理を行う（ス
テップＳ１１４）。ステップＳ１１３で切り出した連結
フラグが’１’ならば、次のセルデータの格納先を示す
アドレスを、現在のセルアドレスレジスタＣＥＬＬＡＤ
Ｒの値とセルサイズとから算出して、セルアドレスレジ
スタＣＥＬＬＡＤＲに書き込む。連結フラグが’０’な
らば、次に連結されるセルは無いため、ｎｕｌｌをセル
アドレスレジスタＣＥＬＬＡＤＲに書き込む。さらに、
セルカウントレジスタＮＵＭＣＥＬＬをデクリメントす
る。このようにしてセルポインタを更新した後、次に、
連結フラグはセルの終了を表すＥＯＣであるかどうかを
判定する（ステップＳ１１５）。ここで連結フラグがセ
ルの継続を表す’１’ならばステップＳ１１６に、ＥＯ
Ｃを表す’０’ならばステップＳ１１７に移るよう、先
の連結フラグの値によって処理フローの切替えを行う。

【０１４１】連結フラグがセルの継続を表す’１’の場
合、ステータスレジスタＳＴＡＴＵＳの内容を調べ、待
機状態であることを表す’１’の値が検出されるかどう
かが判定される（ステップＳ１１６）。ここで、待機状
態の座標点生成回路があると判定されたならば、ステッ
プＳ１１３に戻ってセルアドレスレジスタＣＥＬＬＡＤ
Ｒに格納されているアドレスが示すセルデータの読み出
しを行い、’１’の値が格納されていたビットに対応す
る座標点生成回路５５２Ａ〜５５２Ｄにセルデータの各
値を書き込むといった処理を行う。ステータスレジスタ
ＳＴＡＴＵＳの内容を調べた結果、全ビットの値が’
０’、つまり、すべての座標点生成回路５５２Ａ〜５５
２Ｄは座標点生成処理中である場合は、連結セルが継続
していても次のセルの読み込みを行わない。

【０１４２】待機状態の座標点生成回路がない場合は、
セルアドレスレジスタＣＥＬＬＡＤＲ中の更新セルポイ
ンタの値をプリフェッチレジスタＰＲＥＦＥＴＣＨの現
在処理中のｙバケットに書き込んで更新する（ステップ
Ｓ１１７）。プリフェッチレジスタＰＲＥＦＥＴＣＨの
全ｙバケットデータに対する更新が終了した場合は、ｙ
バケットデータの書き込み要求をメモリコントローラ５
３に出し、メモリコントローラ５３から書き込み許可信
号が来たら、ＹリストアドレスレジスタＹＬＩＳＴＡＤ
Ｒ中のｙリストアドレスを出力し、次にセルアドレスレ
ジスタＣＥＬＬＡＤＲ中の更新セルポインタの値を連続
出力してディスプレイリストバンドバッファ５４１に書
き込みを行い、プリフェッチしたｙバケットにおけるセ
ルポインタを更新する。そして、ｙリストアドレスレジ
スタＹＬＩＳＴＡＤＲの値を次に読み込むｙリストを示
すバッファアドレスに更新する。このようにして、ｙリ
ストの処理が終了したら図３４のステップＳ１０３のセ
ルの処理に移る。なお、ディスプレイリストバンドバッ
ファ５４１への書き込み処理は座標点生成処理中に並行
して行われる。

【０１４３】図３６は第２の実施の形態での座標点生成
ＬＳＩのセルの処理の流れを示すフローチャートであ
る。まず、セルの処理は座標点出力処理で始まる（ステ
ップＳ１２１）。すなわち、エッジリストバッファ５４
２から現在処理中の走査ラインに対してバッファに格納
されているエッジデータ数Ｐｉを読み込み、その数を更
新して、更新したエッジデータ数とエッジデータレジス
タＣＵＲＸｉ（ｉ＝１〜４）に格納したデータとをエッ
ジリストバッファ５４２に書き込む。次に、走査ライン
の更新、それに伴うエッジデータの更新、算出された座
標点のソート処理、ソート結果のエッジデータレジスタ
への格納といったエッジデータ更新処理を行い（ステッ
プＳ１２２）、続いて、座標点生成回路５５２Ａ〜５５
２Ｄの待機状態のチェック、待機状態の座標点生成回路
５５２Ａ〜５５２Ｄがある場合の現在処理中の走査ライ
ンに対するｙバケットの有無のチェック、現在処理中の
走査ラインに対するｙバケットが存在する場合のセルの
読み出しおよびセルポインタの更新といったセル追加判
定処理を行い（ステップＳ１２３）、再度、ステップＳ
１２１と同様の座標点出力処理を行う（ステップＳ１２
４）。

【０１４４】次に、セル処理終了の判定をする（ステッ
プＳ１２５）。すなわち、座標点生成回路５５２Ａ〜５
５２ＤのＥＮＤ信号を管理回路５５１に出力し、各々の
値を管理回路５５１のステータスレジスタＳＴＡＴＵＳ
に書き込む。そして、ステータスレジスタＳＴＡＴＵＳ
の値を調べ、全ビットの値が’１’、つまり、すべての
座標点生成回路５５２Ａ〜５５２Ｄは待機状態であるか
を判定する（ステップＳ１２６）。ここで、すべての座
標点生成回路５５２Ａ〜５５２Ｄが待機状態であるなら
ば、このセルの処理を終了し、図３４のステップＳ１０
４へ移る。一つでも値が’０’のビットがあるならば、
つまり座標点生成処理中の座標点生成回路５５２Ａ〜５
５２Ｄがある場合は、ステップＳ１２２へ移り、座標点
生成処理を継続する。

【０１４５】次に、このセルの処理における座標点出力
処理であるステップＳ１２１，Ｓ１２４の各ステップの
処理内容についてより詳細に説明を行う。図３７は第２
の実施の形態での座標点生成ＬＳＩの座標点出力処理の
流れを示すフローチャートである。座標点出力処理で
は、まず、アドレス計算およびメモリアクセス要求を行
う（ステップＳ１３１）すなわち、現在処理中の走査ラ
インに対するエッジデータ数Ｐｉが格納されているエッ
ジリストバッファアドレスを式（５）に従って算出し、
ＥＬバッファアドレスレジスタＥＬＢＡＤＲにその値を
書き込む。同時に、現在処理中の走査ラインに対する、
エッジリストバッファ５４２に格納されているエッジデ
ータ数Ｐｉの読み出し要求をメモリコントローラ５３に
出力する。次に、メモリコントローラ５３から読み出し
許可信号が来たら、ＥＬバッファアドレスレジスタＥＬ
ＢＡＤＲの値をメモリコントローラ５３に出力する（ス
テップＳ１３２）。次に、メモリコントローラ５３がメ
モリ５４のエッジリストバッファ５４２からエッジデー
タ数Ｐｉを読み出すと、そのエッジデータ数Ｐｉを読み
込み、一旦フェッチレジスタＦＥＴＣＨに格納する（ス
テップＳ１３３）。

【０１４６】次に、読み込んだエッジデータ数Ｐｉに座
標点生成回路の数である’４’を加えてメモリ５４へ書
き戻す（ステップＳ１３４）。すなわち、まず、フェッ
チレジスタＦＥＴＣＨの値を読み出し、座標点生成回路
５５２Ａ〜５５２Ｄで一走査ライン毎に生成される座標
点の数の４を読み出した値に加えて、その値をメモリコ
ントローラ５３に出力し、エッジリストバッファ５４２
の読み込み時と同じアドレスに書き戻す。さらに、ＥＬ
バッファアドレスレジスタＥＬＢＡＤＲの値とフェッチ
レジスタＦＥＴＣＨの値（４を加える前の値）から現在
処理中の走査ラインに対するエッジデータを格納する先
のアドレスを算出し、更新エッジデータ数の出力後、そ
のアドレスをメモリコントローラ５３へ出力する。な
お、内部バスのアービトレーション機能により、ステッ
プＳ１２１およびステップＳ１２４の処理中はカード内
部バスおよびメモリ５４へのアクセス権は座標点生成Ｌ
ＳＩ５５が保持したままである。

【０１４７】最後に、エッジデータをメモリ５４へ書き
込む（ステップＳ１３５）。すなわち、管理回路５５１
のカレントＸｉレジスタＣＵＲＸｉ（ｉ＝１〜４）に格
納されている現在処理中の走査ラインに対する各ｘ座標
値を同時に読み出し、各データは昇順に配置された状態
で、ステップＳ１３４でのアドレス出力後にメモリコン
トローラ５３に出力し、エッジリストバッファ５４２の
ステップＳ１２４で出力したアドレスの示す領域に四つ
のｘ座標値を書き込む。このようにして、行われた座標
点出力処理が図３６のステップＳ１２１ならば、処理は
図３６のステップＳ１２２に移り、図３６のステップＳ
１２４であれば、図３６のステップＳ１２５に処理が移
る。

【０１４８】次に、図３６のステップＳ１２２における
エッジデータ更新処理について図３８により詳細に説明
する。図３８は第２の実施の形態での座標点生成ＬＳＩ
のエッジデータ更新処理の流れを示すフローチャートで
ある。エッジデータ更新処理では、まず、処理の終了し
た走査ラインに対するｙ座標値を管理回路５５１のカレ
ントｙレジスタＣＵＲＹから読み出し、その値に１を加
えてレジスタＣＵＲＹに書き戻し、処理を行う走査ライ
ンを更新する（ステップＳ１４１）。次に、座標点生成
回路５５２Ａ〜５５２Ｄのうち処理継続中である座標点
生成回路において、図３１に示す、Ｘレジスタ、ΔＸレ
ジスタ、ΔＹレジスタより座標点生成回路内の演算回路
５５２３，５５２４に入力されているＸ，ΔＹ，ΔＸの
値から、ΔＹのデクリメント処理およびＸとΔＸとの加
算処理をそれぞれ行ってΔＹ，Ｘの各値を更新し、ＬＤ
信号を’１’にして各レジスタに書き込むという処理を
行う（ステップＳ１４２）。

【０１４９】その後、座標点生成回路５５２の演算回路
５５２７により、ステップＳ１４２で更新されたＸレジ
スタの値を整数化して、部分ソート回路５５３に出力す
る（ステップＳ１４３）。待機中、つまり、ステータス
レジスタＳＴＡＴＵＳの値が’１’の座標点生成回路５
５２Ａ〜５５２Ｄから部分ソート回路５５３へ出力され
るデータは、先述した通り座標点生成回路５５２のマル
チプレクサ５５２９により最大値となる。そして、部分
ソート回路５５３において、入力された四つのｘ座標値
を先述した処理に従って昇順にソートし、その結果を管
理回路５５１に出力して管理回路５５１のカレントｘレ
ジスタＣＵＲＸｉ（ｉ＝１〜４）に格納する（ステップ
Ｓ１４４）。このようにしてエッジデータ更新処理のス
テップＳ１２２の処理が終了したら、図３６のステップ
Ｓ１２３のセル追加判定処理に移る。このセル追加判定
処理の詳細を図３９を参照して詳細に説明する。

【０１５０】図３９は第２の実施の形態での座標点生成
ＬＳＩのセル追加判定処理の流れを示すフローチャート
である。セル追加判定処理では、まず、セルカウンタレ
ジスタＮＵＭＣＥＬＬの値により、追加するセルが残っ
ているかどうかを調べる（ステップＳ１５１）。セルカ
ウンタレジスタＮＵＭＣＥＬＬの値が０の場合は、追加
するセルはないということなので、このセル追加判定処
理を終了して処理を図３６のステップＳ１２４に移す。
セルカウンタレジスタＮＵＭＣＥＬＬの値が０でない場
合は、待機状態の座標点生成回路があるかどうかを判定
する（ステップＳ１５２）。ここでは、ステータスレジ
スタＳＴＡＴＵＳの内容を調べた結果、全ビットの値
が’０’、つまり、すべての座標点生成回路５５２Ａ〜
５５２Ｄが座標点生成処理中である場合は、このセル追
加判定処理を終了して図３６のステップＳ１２４に処理
を移す。もし、ステータスレジスタＳＴＡＴＵＳの内容
を調べて待機状態であることを表す’１’の値が検出さ
れたならば、ｙバケットレジスタＹＢＵＣＫＥＴに格納
されているｙバケットデータのｙ座標値ｙ_nextとカレン
トｙレジスタＣＵＲＹに格納されている現在処理中の走
査ラインのｙ座標値との比較を行う（ステップＳ１５
３）。その比較の結果、ｙバケットレジスタＹＢＵＣＫ
ＥＴのｙ座標値ｙ_nextがカレントｙレジスタＣＵＲＹの
ｙ座標値より大きければ、このセル追加判定処理を終了
して図３６のステップＳ１２４に処理を移す。もし、ｙ
バケットレジスタＹＢＵＣＫＥＴのｙ座標値がカレント
ｙレジスタＣＵＲＹの値より小さければ、ステップＳ１
５４に移り、ｙバケットレジスタＹＢＵＣＫＥＴのｙ座
標値がカレントｙレジスタＣＵＲＹの値と等しければ、
ｙバケットレジスタＹＢＵＣＫＥＴの内容をフェッチレ
ジスタＦＥＴＣＨに書き込み、更にプリフェッチレジス
タＰＲＥＦＥＴＣＨから次のｙバケットデータをｙバケ
ットレジスタＹＢＵＣＫＥＴに格納してステップＳ１６
０に移る。

【０１５１】ステップＳ１５３での比較の結果、ｙバケ
ットレジスタＹＢＵＣＫＥＴのｙ座標値がカレントｙレ
ジスタＣＵＲＹの値より小さいと判定された場合には、
ｙバケットデータが比較部５５１１１に読み込まれた回
数をカウントするｙリストカウンタレジスタＹＣＯＵＮ
Ｔをインクリメントする（ステップＳ１５４）。次に、
プリフェッチデータの更新の必要性を判定する（ステッ
プＳ１５５）。すなわち、プリフェッチ部５５１１０に
プリフェッチされたｙバケットデータがすべて比較部５
５１１１に読み込まれたかどうかを、ｙリストカウンタ
レジスタＹＣＯＵＮＴの値とプリフェッチ数ｍとから判
別し、すべて読み込まれている場合にはプリフェッチデ
ータを更新する必要があると判定される。更新の必要が
ある場合には、ステップＳ１５６に、そうでない場合は
プリフェッチレジスタＰＲＥＦＥＴＣＨから次のｙバケ
ットデータをフェッチレジスタＦＥＴＣＨに格納してス
テップＳ１５７に移る。

【０１５２】ステップＳ１５５において、プリフェッチ
データを更新すると判定された場合には、ｍバケット分
のｙバケットデータをプリフェッチする（ステップＳ１
５６）。すなわち、ｙリストアドレスレジスタＹＬＩＳ
ＴＡＤＲの値をフェッチレジスタＦＥＴＣＨに読み出し
て次のｍ個のｙバケットの読み出し要求をメモリコント
ローラ５３に出す。メモリコントローラ５３から読み出
し許可信号が来たら、フェッチレジスタＦＥＴＣＨに読
み出したｙリストアドレスをメモリコントローラ５３に
出力してｍ個のｙバケットデータの連続読み出しを行
う。読み出されたデータはプリフェッチレジスタＰＲＥ
ＦＥＴＣＨに格納し、ｙリストカウンタレジスタＹＣＯ
ＵＮＴのカウント値に対応したｙバケットデータをフェ
ッチレジスタＦＥＴＣＨに格納する。

【０１５３】次に、ステップＳ１５５またはステップＳ
１５６にて、フェッチレジスタＦＥＴＣＨに格納したｙ
バケットデータからｙ座標値ｙ_i の切り出しを行い、カ
レントｙレジスタＣＵＲＹの値との比較を行う（ステッ
プＳ１５７）。その比較の結果、切り出したｙ座標値ｙ
_i がカレントｙレジスタＣＵＲＹの値より小さかった場
合にはステップＳ１５８に、大きかった場合にはステッ
プＳ１５９に、または等しかった場合にはステップＳ１
６０に処理が移る。

【０１５４】ステップＳ１５７での判定にて、ｙ座標値
ｙ_i がカレントｙレジスタＣＵＲＹの値より小さかった
場合、ｙリストカウンタレジスタＹＣＯＵＮＴとｙリス
トの総数を表すトータルｙリストレジスタＮＵＭＬＩＳ
Ｔの値との比較が行われる（ステップＳ１５８）。その
比較の結果、両者の値が等しくない（ＹＣＯＵＮＴの値
がＮＵＭＬＩＳＴの値より小さい）場合は、ｙリストア
ドレスレジスタＹＬＩＳＴＡＤＲの値を次に読み込むｙ
リストを示すバッファアドレスに更新し、ステップＳ１
５４に戻って、次のｙリストの読み込みを行い、等しい
場合には、ｙリストカウンタレジスタＹＣＯＵＮＴの値
を０リセットし、更にｙリストトップアドレスレジスタ
ＹＬＴＯＰＡＤＲの内容をｙリストアドレスレジスタＹ
ＬＩＳＴＡＤＲに読み込んで、このセル追加判定処理を
終了して処理を図３６のステップＳ１２４に移す。

【０１５５】ステップＳ１５７での判定にて、ｙ座標値
ｙ_i がカレントｙレジスタＣＵＲＹの値より大きかった
場合、ステップＳ１５６でフェッチレジスタＦＥＴＣＨ
に格納した、ｙ_i ＞ＣＵＲＹとなったｉ番目のｙバケッ
トデータの値をｙバケットレジスタＹＢＵＣＫＥＴに格
納する（ステップＳ１５９）。これは、処理する走査ラ
インの更新後、追加判定処理が発生した場合に、毎回ｙ
リストの読み込みを行ってカレントｙレジスタＣＵＲＹ
の値と等しいｙ座標値を持つｙバケットを探さなくても
よいようにするために必要な処理である。その後、この
セル追加判定処理を終了して処理を図３６のステップＳ
１２４に移す。

【０１５６】ステップＳ１５７での判定にて、ｙ座標値
ｙ_i がカレントｙレジスタＣＵＲＹの値に等しかった場
合、次のセルデータを読み込む（ステップＳ１６０）。
すなわち、ステップＳ１５５またはステップＳ１５６で
フェッチレジスタＦＥＴＣＨに格納したｙバケットデー
タからエッジセルへのポインタの切り出しを行い、その
値をセルアドレスレジスタＣＥＬＬＡＤＲに格納する。
そして、セルデータの読み出し要求をメモリコントロー
ラ５３に出し、メモリコントローラ５３から読み出し許
可信号が来たら、セルアドレスレジスタＣＥＬＬＡＤＲ
の値をメモリコントローラ５３に出力して一つのセルデ
ータの読み出しを行う。読み出されたデータは一旦フェ
ッチレジスタＦＥＴＣＨに格納され、開始点を表すｘ座
標値、ｘ座標値の増分Δｘ、エッジと交差する走査ライ
ン数を表すΔｙの値、および次のセルの継続状態を示す
連結フラグをそれぞれ切り出し、待機中の座標点生成回
路に連結フラグ以外の各データを転送して、ｘ座標値を
Ｘレジスタに、ΔｘをΔＸレジスタに、ΔｙをΔＹレジ
スタにそれぞれ格納する。なお、この時、データが転送
された座標点生成回路から出力されるＥＮＤ信号は’
０’となり、ステータスレジスタＳＴＡＴＵＳの当該座
標点生成回路に対応するビットにも’０’が書き込まれ
て、その座標点生成回路は待機状態ではなくなったこと
を示す。データ転送後、座標点生成回路５５２Ａ〜５５
２Ｄは、現在処理中の走査ラインに対するエッジの座標
点を生成してその値を部分ソート回路５５３に出力し、
部分ソート回路５５３によってソートされた各座標点デ
ータを管理回路５５１のエッジデータレジスタＣＵＲＸ
ｉ（ｉ＝１〜４）に格納する。

【０１５７】次に、セルポインタの更新を行う（ステッ
プＳ１６１）。ここでは、ステップＳ１６０で切り出し
た連結フラグが’１’ならば、次のセルデータの格納先
を示すアドレスを現在のセルアドレスレジスタＣＥＬＬ
ＡＤＲの値とセルサイズとから算出してセルアドレスレ
ジスタＣＥＬＬＡＤＲに書き戻す。もし、連結フラグ
が’０’ならば、次に連結されるセルはないため、ｎｕ
ｌｌをセルアドレスレジスタＣＥＬＬＡＤＲに書き込
む。さらに、セルカウントレジスタＮＵＭＣＥＬＬをデ
クリメントする。このようにしてセルポインタを更新し
た後、その連結フラグはＥＯＣを表す’０’であったか
どうかの判定が行われる（ステップＳ１６２）。判定の
結果、連結フラグが’０’でない場合には、待機状態の
座標点生成回路があるかどうかを判定する（ステップＳ
１６３）。ここでは、ステータスレジスタＳＴＡＴＵＳ
の内容を調べ、待機状態であることを表す’１’の値が
検出されたならば、ステップＳ１６０に戻って、セルア
ドレスレジスタＣＥＬＬＡＤＲに格納されているアドレ
スが示すセルデータの読み出しを行い、’１’の値が格
納されていたビットに対応する座標点生成回路にセルデ
ータの各値を書き込むといった処理を行う。ステータス
レジスタＳＴＡＴＵＳの内容を調べた結果、全ビットの
値が’０’、つまり、すべての座標点生成回路５５２Ａ
〜５５２Ｄは座標点生成処理中である場合は、連結セル
が継続していても次のセルの読み込みを行わない。

【０１５８】ステップＳ１６２において連結セルがない
と判定された場合、またはステップＳ１６３においてす
べての座標点生成回路５５２Ａ〜５５２Ｄが座標点生成
処理中であると判定された場合には、セルアドレスレジ
スタＣＥＬＬＡＤＲ中の更新セルポインタの値をプリフ
ェッチレジスタＰＲＥＦＥＴＣＨの現在処理中のｙバケ
ットに書き込んで更新する（ステップＳ１６４）。プリ
フェッチレジスタＰＲＥＦＥＴＣＨの全ｙバケットデー
タに対する更新が終了した場合は、ｙバケットデータの
書き込み要求をメモリコントローラ５３に出し、メモリ
コントローラ５３から書き込み許可信号が来たら、ｙリ
ストアドレスレジスタＹＬＩＳＴＡＤＲ中のｙリストア
ドレスを出力し、次に、セルアドレスレジスタＣＥＬＬ
ＡＤＲ中の更新セルポインタの値を連続出力してディス
プレイリストバンドバッファ５４１に書き込みを行い、
プリフェッチしたｙバケットにおけるセルポインタを更
新する。そして、ｙリストアドレスレジスタＹＬＩＳＴ
ＡＤＲの値を次に読み込むｙリストを示すバッファアド
レスに更新する。なお、ディスプレイリストバンドバッ
ファ５４１への書き込み処理は座標点生成処理中に並行
して行われる。このようにして、このセル追加判定処理
を終了すると、処理は図３６のステップＳ１２４に移
る。

【０１５９】次に、座標点生成ＬＳＩ５５によってＣＰ
Ｕ５０に当該描画オブジェクトに対する座標点生成処理
が終了したことが通知されると、ＣＰＵ５０はエッジリ
ストバッファ５４２のエッジリスト部に格納されている
走査ライン毎のｘ座標値のソート処理を開始する。第２
の実施の形態では、エッジリスト部に格納されている走
査ライン毎のｘ座標値は、先述した通り既に部分ソート
回路５５３により４個ずつ昇順にソートされており、大
部分はソート部２０でのソート処理を必要としないほど
ソートされている。したがって、ソート部２０でのソー
ト処理は図２４〜図２７で述べたクイックソートプログ
ラムである必要はなく、ソートがほとんど済んでいると
いう条件を活かすことのできるソート処理方法を用いる
ことが望ましい。そこで、以下に本発明の第２の実施の
形態におけるソート部２０の好適な処理内容について詳
細に説明する。

【０１６０】発明の第２の実施の形態におけるソート部
２０の全体的な処理の流れは、図２４の処理の流れと同
様であるのでここでは説明を省略する。但し、図２４の
ステップＳ７５での設定値は、第２の実施の形態におい
ては、４となる。

【０１６１】図４０は第２の実施の形態でのソート部に
おけるソート方法の概念を示す説明図である。まず、入
力されたｎ個のエッジデータは４個ずつ読み込まれる。
ここで、２組のエッジデータＥＤ_N ，ＥＤ_N+1 のそれぞ
れに関して、先頭のエッジデータＥＤ_N(1)，ＥＤ_N+1(1)
の大小比較を行い、小さい方（仮に、ＥＤ_N(1)とする）
をバッファに書き込む。次に、残ったエッジデータＥＤ
_N+1(1)と、次のエッジデータＥＤ_N(2)の大小比較を行
い、小さい方（仮に、ＥＤ_N+1(1)とする）をバッファに
書き込む。上記の処理を繰り返し行い、８個すべてのエ
ッジデータを、値の小さい順にソートする。

【０１６２】さらに、読み込むエッジデータの数を４ｎ
（ｎ＝１，２・・・）個として、上記の処理を行うこと
により、すべてのエッジデータをソートすることが可能
となる。

【０１６３】次に、ソート部でこの上述したソート方法
を実現するソフトウェアの機能構成について説明する。
図４１は第２の実施の形態でのソート部の構成例を示す
ブロック図である。ソート部は、エッジデータ入力部２
０１と、ソートバッファ２０２と、エッジデータ出力部
２０３と、ソート処理管理部２０４と、部分エッジデー
タ取得部２０８と、部分エッジデータ判定部２０９と、
部分エッジデータ併合部２１０とから構成される。

【０１６４】エッジデータ入力部２０１はエッジリスト
バッファ５４２からエッジリストバッファアドレスが示
すバッファ内のエッジデータを入力する。ソートバッフ
ァ２０２はエッジデータ入力部２０１に入力したエッジ
データを一時的に蓄える。エッジデータ出力部２０３は
最終的にソートされたエッジデータをソートバッファ２
０２からエッジリストバッファ５４２へ出力する。ソー
ト処理管理部２０４はソートすべきエッジデータ数の設
定などのソート処理全体を管理する。部分エッジデータ
取得部２０８はエッジデータ入力部２０１で入力された
エッジデータをｎ個ずつ読み込む。部分エッジデータ判
定部２０９は部分エッジデータ取得部２０８で読み込ん
だそれぞれのエッジデータの大小を判定する。そして、
部分エッジデータ併合部２１０は部分エッジデータ判定
部２０９の比較判定結果に従い、エッジデータを併合し
て書き込む機能を有している。

【０１６５】次に、図４１に示したように構成されるソ
ート部におけるソート処理の流れを図４２のフローチャ
ートを用いて詳細に説明する。図４２は第２の実施の形
態でのソート部の処理の流れを示すフローチャートであ
る。エッジデータ入力部２０１で入力されたエッジデー
タは、まず、ソートバッファ２０２に蓄えられる。ここ
で、ソート処理が開始されると、まず、部分エッジデー
タ取得部２０８はエッジデータ数が４以下かどうかを判
定する（ステップＳ１７１）。エッジデータ数が４以下
なら終了し、４より大きければ、部分エッジデータ取得
部２０８により、個数４ｍ（ｍ＝１）のエッジデータが
２組読み込まれる（ステップＳ１７２）。次に、部分エ
ッジデータ判定部２０９により、２組のエッジデータＥ
Ｄ₁(i)，ＥＤ₂(j)のそれぞれのエッジデータ値の大小比
較を行う（ステップＳ１７３）。部分エッジデータ併合
部２１０により、これら２組のエッジデータＥＤ₁(i)，
ＥＤ₂(j)の内、値の小さいエッジデータをソートバッフ
ァ２０２へ書き込む。すなわち、大小比較の結果、エッ
ジデータＥＤ₁(i)がエッジデータＥＤ₂(j)より小さい場
合には、エッジデータＥＤ₁(i)を書き込み（ステップＳ
１７４）、エッジデータＥＤ₂(j)がエッジデータＥＤ
₁(i)より小さい場合には、エッジデータＥＤ₂(j)を書き
込む（ステップＳ１７５）。次いで、ソート処理管理部
２０４はｉまたはｊをそれぞれインクリメントし（ステ
ップＳ１７６，Ｓ１７７）、ｉまたはｊをそれぞれｎと
比較する（ステップＳ１７８，Ｓ１７９）。比較の結
果、ｉまたはｊがｎより小さい間は、ステップＳ１７３
に戻る。このようにして、ソート処理管理部２０４は、
部分エッジデータ取得部２０８で読み込んだエッジデー
タ列のすべてのエッジデータの大小比較を行うように管
理する。

【０１６６】次に、２組のエッジデータＥＤ₁(i)，ＥＤ
₂(j)の内、いずれか一方の組のエッジデータ列がすべて
書き込まれた場合は、部分エッジデータ併合部２１０に
より、他方の組のエッジデータ列の残りすべてのエッジ
データをソートバッファ２０２へ書き込む（ステップＳ
１８０）。ここで、ｎ個ずつ２組読み込めるエッジデー
タがあるかどうかが判定される（ステップＳ１８１）。
もし、ｎ個ずつ２組読み込めるエッジデータがある場合
には、ステップＳ１７２に戻り、新しいエッジデータの
読み込みを行う。ｎ個ずつ２組読み込めるエッジデータ
がなければ、ソート処理管理部２０４は、部分エッジデ
ータ取得部２０８で読み込むエッジデータ列の個数を変
更する（ステップＳ１８２）。そして、ソート処理管理
部２０４により、エッジデータ数がｎより小さいかどう
かが判定される（ステップＳ１８３）。エッジデータ数
がｎより大きい間は、ステップＳ１７２に戻って、以上
の処理を繰り返す。ステップＳ１８３の判定にて、エッ
ジデータ数がｎより小さくなると、このソート処理は終
了する。これにより、エッジリストバッファ５４２から
入力された個数のエッジデータすべてに対して、ｘの値
の小さい順にソートされることになる。

【０１６７】上記の処理がすべて終了し、ソートバッフ
ァ中の全エッジデータがソートされると、エッジデータ
出力部２０３は、エッジリストバッファ５４２にソート
バッファ２０２中のエッジデータおよびソート処理管理
部２０４で管理されている最大値を除いた有効なエッジ
データ数を出力する。

【０１６８】以上の二つの実施の形態では、座標点生成
の処理に必要なエッジの傾き情報、すなわち、Δｘは浮
動小数点データになるので、座標点生成回路には傾き情
報を整数値へ変換する演算器を備えているが、次に、傾
き情報をあらかじめ整数化して座標点生成を行うように
した本発明の第３の実施の形態について説明する。

【０１６９】図４３は第３の実施の形態でのディスプレ
イリストの連結セルの構成を示す図である。ディスプレ
イリストのヘッダ部およびｙバケットは、図１２および
図１３で示したディスプレイリストのヘッダ部およびｙ
バケットの構成と同様であるので、ここでは説明を省略
する。連結セルは、入力された各描画オブジェクト毎の
ベクタデータの始点のｘ座標値と、ベクタデータの終点
のｘ座標値と始点のｘ座標値との差分であるｄｘと、ベ
クタデータの終点のｙ座標値と始点のｙ座標値との差分
であるｄｙと、ベクタデータと交差する走査ラインの数
であるΔｙと、その走査ラインｙを始点とする異なるベ
クタデータが存在するか否かを示す連結フラグとから構
成される。これらの内、ｘ，ｄｘ，ｄｙ，Δｙは、すべ
て整数で表される。複数のバンドにまたがる描画オブジ
ェクトは、バンドの境界で複数のオブジェクトに分割さ
れるため、ｄｙとΔｙは異なる値を持つ。複数のバンド
にまたがらない描画オブジェクトでは、各連結セルのｄ
ｙとΔｙは等しい。

【０１７０】次に、第３の実施の形態における座標点生
成ＬＳＩ５５について詳細に説明する。座標点生成ＬＳ
Ｉ５５は、たとえば図２９に示した構成のものを使用す
ると、管理回路５５１と、四つの座標点生成回路５５２
Ａ〜５５２Ｄと、部分ソート回路５５３とから構成され
る。これらの構成要素の内、管理回路５５１および部分
ソート回路５５３は、第２の実施の形態で述べたものと
同様である。ただし、本実施の形態でのディスプレイリ
ストは、図４３に示したように、第２の実施の形態のも
のとは異なるので、管理回路５５１から座標点生成回路
５５２へ転送されるセルデータは（Ｘ，ＤＸ，ＤＹ，Δ
Ｙ）となっている。座標点生成回路５５２Ａ〜５５２Ｄ
は、管理回路５５１から１組ずつ上記セルデータを入力
し、走査ライン毎に同期して最大４点のエッジデータを
並列に生成する機能を備えるものである。四つの座標点
生成回路５５２Ａ〜５５２Ｄは、すべて同一の構造を持
つ。このように、第３の実施の形態での座標点生成回路
５５２は、座標点計算がすべて整数演算のみで実行でき
るように工夫されている。

【０１７１】図４４は第３の実施の形態での座標点生成
回路の構成例を示すブロック図である。座標点生成回路
５５２は、初期値計算部５５４と、座標点計算部５５５
とから構成される。初期値計算部５５４は、管理回路５
５１からセルデータのＤＸとＤＹとを入力し、誤差の初
期値Ｅ0 と、誤差Ｅが正の時にＸに加算される値ＤＸＰ
と、誤差Ｅが負の時にＸに加算される値ＤＸＮと、誤差
Ｅが正の時にＥに加算される値ＤＥＰと、誤差Ｅが負の
時にＥに加算される値ＤＥＮを計算し、座標点計算部５
５５へ出力するものである。座標点計算部５５５は、
Ｘ，ＤＸＰ，ＤＸＮ，Ｅ0 ，ＤＥＰ，ＤＥＮ，ΔＹを用
いて走査ライン毎にエッジの座標点を計算するものであ
る。

【０１７２】図４５は第３の実施の形態での座標点生成
処理の様子を示す説明図である。誤差Ｅとは、走査ライ
ン毎に行われる座標点計算において、座標値Ｘの増分を
決定するために用いる数である。ＤＸ／ＤＹの小数点以
下を切り捨てた数を基本増分Δとし、エッジと走査ライ
ンとの交点をＰ、Ｘ_i＋ΔとＸ_i＋Δ＋１との中点をＱと
すれば、誤差Ｅｉは、交点Ｐと中点Ｑとの差分（Ｐ−
Ｑ）と定義される。ここで、エッジが図４５に示したよ
うに例えば中点Ｑよりも右側で走査ラインと交差してい
るとき、すなわち、Ｅ_i＞０の場合は、Ｘ_i+1＝Ｘ_i＋Δ
＋１となり、逆に、Ｅ_i＜０の場合はＸ_i＋１＝Ｘ_i＋Δ
となる。また、誤差Ｅ自身も走査ライン毎に更新され、
Ｅ_i＞０の場合はＥ_i+1＝Ｅ_i＋２ｄｘ−２ｄｙ（Δ＋
１）となり、Ｅ_i＜０の場合はＥ_i+1＝Ｅ_i＋２ｄｘ−２
ｄｙΔとなる。走査ライン毎にＸあるいはＥに加えられ
る値は、既に述べたように、あらかじめ初期値計算部５
５４で計算され、座標点計算部５５５の内部レジスタに
格納される。初期値の計算式は式（７）に示す通りであ
る。ただし、符号はΔ＞０の時、＋をとり、Δ＜０の時
は−をとる。

【０１７３】

【数７】 ＤＸＮ＝Δ＝ＤＸ／ＤＹ ……（７ａ） ＤＸＰ＝Δ±１ ……（７ｂ） Ｅ0 ＝２・ＤＸ−ＤＹ−２・ＤＹ・Δ ……（７ｃ） ＤＥＮ＝２・ＤＸ−２・ＤＹ・Δ ……（７ｄ） ＤＥＰ＝２・ＤＸ−２・ＤＹ・（Δ±１） ……（７ｅ） 次に、図４４に示した座標点生成回路５５２の初期値計
算部５５４の構成例について説明する。

【０１７４】図４６は初期値計算部の構成例を示すブロ
ック図である。初期値計算部５５４は、セルデータ（Ｄ
Ｘ，ＤＹ）を保持するＤＸレジスタ５５４１およびＤＹ
レジスタ５５４２と、加減算器５５４３と、シフトレジ
スタ５５４４と、計算結果の初期値を一時的に保持する
ＴＭＰレジスタ５５４５と、二つのマルチプレクサ５５
４６および５５４７とから構成される。加減算器５５４
３とシフトレジスタ５５４４との組合せにより、乗算お
よび除算を実行することができる。また、加減算器５５
４３はインクリメンタとデクリメンタの機能を持つ。Ｄ
Ｘレジスタ５５４１、ＤＹレジスタ５５４２およびＴＭ
Ｐレジスタ５５４５は、１ビット左シフトの操作ができ
るように構成されている。各レジスタへの書き込み、シ
フトの開始／終了、加減算器５５４３の処理の切り替
え、各マルチプレクサの切り替え等は、図示しない制御
信号によって管理回路５５１から制御される。初期値計
算部５５４は、この構成により、セルデータ（ＤＸ，Ｄ
Ｙ）を入力し、式（７）に従った計算を行うことにより
初期値であるＤＸＮ，ＤＸＰ，Ｅ0 ，ＤＥＮ，ＤＥＰを
出力するが、この初期値計算部５５４における計算処理
の流れを図４７を用いて説明する。

【０１７５】図４７は初期値計算部の処理の流れを示す
フローチャートである。まず、ＤＸレジスタ５５４１お
よびＤＹレジスタ５５４２にセルデータＤＸ，ＤＹが入
力されると、まず、加減算器５５４３とシフトレジスタ
５５４４を用いてＤＸ／ＤＹの整数除算を行い、初期値
ＤＸＮを計算して出力する（ステップＳ１９１）。この
時、同時にＴＭＰレジスタ５５４５にもＤＸＮの値を格
納しておく。次に、ＴＭＰレジスタ５５４５の符号ビッ
トの値に応じて加減算器５５４３におけるインクリメン
トとデクリメントを切り替え、初期値ＤＸＰを計算して
出力する（ステップＳ１９２）。このとき、ＴＭＰレジ
スタ５５４５の符号ビットの値、すなわちΔの符号は、
初期値計算が終了するまで図示しないステートマシンの
ステータスレジスタに記憶しておく。次に、加減算器５
５４３とシフトレジスタ５５４４とを用いて、ＤＹ×Ｔ
ＭＰの乗算を行い、結果をＴＭＰレジスタ５５４５に格
納する（ステップＳ１９３）。このとき、ＤＸレジスタ
５５４１を左シフトしておく。

【０１７６】次に、ＴＭＰレジスタ５５４５を左シフト
し、その結果を用いて初期値ＤＥＮを計算して出力する
（ステップＳ１９４）。このとき、同時にＴＭＰレジス
タ５５４５にもＤＥＮの値を格納しておく。次に、ＴＭ
Ｐレジスタ５５４５に格納したＤＥＮとＤＹレジスタ５
５４２の値とを用いて、初期値Ｅ0 を計算して出力する
（ステップＳ１９５）。最後に、ＤＹレジスタ５５４２
を左シフトし、その結果とＴＭＰレジスタ５５４５に格
納したＤＥＮとを用いて初期値ＤＥＰを計算して出力す
る（ステップＳ１９６）。以上の初期値計算処理は、始
点の座標点出力処理と並列に実行される。

【０１７７】次に、図４４に示した座標点生成回路５５
２の座標点計算部５５５の構成例について説明する。図
４８は座標点計算部の構成例を示すブロック図である。
座標点計算部５５５は、ｘ座標値を保持するＸレジスタ
５５５０１と、ＤＸＰを保持するＤＸＰレジスタ５５５
０２と、ＤＸＮを保持するＤＸＮレジスタ５５５０３
と、誤差Ｅを保持するＥレジスタ５５５０４と、ＤＥＰ
を保持するＤＥＰレジスタ５５５０５と、ＤＥＮを保持
するＤＥＮレジスタ５５５０６と、交差数ΔＹを保持す
るΔＹレジスタ５５５０７と、二つの加算器５５５０８
および５５５０９と、ΔＹレジスタ５５５０７の値をデ
クリメントする演算器５５５１０と、ΔＹレジスタ５５
５０７の値を０と比較する比較器５５５１１と、Ｅレジ
スタ５５５０４の符号ビットを切り出す演算器５５５１
２と、六つのマルチプレクサ５５５１３〜５５５１８と
から構成される。初期値計算部５５４から順次入力され
る初期値は、図示しないセレクタ回路によって適切なレ
ジスタへ入力され、格納される。各レジスタへの書き込
み、各マルチプレクサの切り替え等は、図示しない制御
信号によって管理回路５５１から制御される。座標点計
算部５５５における走査ライン毎の座標点計算処理は、
以下の式（８ａ）〜（８ｅ）に従って実行される。

【０１７８】

【数８】 Ｘ＝Ｘ＋ＤＸＰ （Ｅ≧０のとき） ……（８ａ） Ｘ＝Ｘ＋ＤＸＮ （Ｅ＜０のとき） ……（８ｂ） Ｅ＝Ｅ＋ＤＥＰ （Ｅ≧０のとき） ……（８ｃ） Ｅ＝Ｅ＋ＤＥＮ （Ｅ＜０のとき） ……（８ｄ） ΔＹ＝ΔＹ−１ ……（８ｅ） まず、Ｘレジスタ５５５０１、ＤＸＰレジスタ５５５０
２、ＤＸＮレジスタ５５５０３、および加算器５５５０
８を使い、演算器５５５１２の出力結果に従ってマルチ
プレクサ５５５１６を切り替えることにより、式（８
ａ）および（８ｂ）の計算が行われる。同様に、Ｅレジ
スタ５５５０４、ＤＥＰレジスタ５５５０５、ＤＥＮレ
ジスタ５５５０６、および加算器５５５０９を使い、演
算器５５５１２の出力結果に従ってマルチプレクサ５５
５１７を切り替えることにより、式（８ｃ）および（８
ｄ）の計算が行行われる。そして、ΔＹレジスタ５５５
０７および演算器５５５１０により式（８ｅ）の計算が
行われる。マルチプレクサ５５５１８は、座標点生成回
路５５２がエッジデータ生成処理をしている場合は、式
（８ａ）または（８ｂ）に従って更新されたＸレジスタ
５５５０１の値を出力し、待機中である場合は、ｘ座標
値の取り得る最大値を出力する。このようにして得られ
たｘ座標値は次段の部分ソート回路５５３に出力され
る。

【０１７９】

【発明の効果】以上説明したように本発明では、所定の
描画命令で記述されている印刷データをディスプレイリ
ストに変換し、ディスプレイリストからビットマップ展
開する印刷処理装置のエッジリストデータ生成処理を、
描画オブジェクトのエッジを表す座標点を生成する座標
点生成処理と、座標点に順序を付けるソート処理とに分
離し、最初に複数の座標点生成装置で繰り返し座標点生
成した後、ソート処理を行うよう構成した。このため、
それぞれの処理に適した処理資源、すなわち、座標点生
成処理はハードウェア、ソート処理はソフトウェアで処
理することが可能となり、記述言語で記述される複雑な
描画オブジェクトに対しても軽い資源で高速の処理を行
うことが可能となり、座標点生成およびソート処理をソ
フトウェアで処理する場合に比べて１０ないし１５倍高
速になる。

【０１８０】また、第２の実施の形態では、複数の座標
点生成装置に、複数の座標点生成装置から一度に出力さ
れる座標点群に対して部分的なソート処理を実行するハ
ードウェアを付加するよう構成した。このため、ソフト
ウェアで実行されるソート処理の負荷を軽減することが
可能になり、一層の高速化が実現できる。さらに、第２
の実施の形態では、複数の座標点生成装置に待機状態が
発生した場合、エッジ情報を追加するよう構成したた
め、複数の座標点生成装置を有効に利用することが可能
となり、複数の座標点生成装置の繰り返し回数が低減
し、座標点生成処理のさらなる高速化が可能となる。

【０１８１】また、本発明を適用することにより、第１
の実施の形態での実装例で示されているようにディスプ
レイリストからビットマップ展開するまでの処理を一体
の回路基板上に構成することが可能となる。このため、
データ量が急増するディスプレイリスト以降の処理に対
して専用の高速バスを設けることが可能となり、ディス
プレイリストからビットマップ展開するまでの処理全体
の高速化を実現することができる。

【図面の簡単な説明】

【図１】本発明による印刷処理装置の原理的な構成を示
す図である。

【図２】本発明の印刷処理装置の全体的な構成を示すブ
ロック図である。

【図３】印刷処理装置における印刷処理の流れを示すフ
ローチャートである。

【図４】印刷処理装置全体が実装されるコンピュータシ
ステムのハードウェア構成例を示した図である。

【図５】描画処理カードのハードウェア構成例を示した
図である。

【図６】印刷処理装置全体が実装される他のコンピュー
タシステムのハードウェア構成例を示した図である。

【図７】描画処理ボードのハードウェア構成例を示した
図である。

【図８】印刷データ解釈部の構成を示すブロック図であ
る。

【図９】ディスプレイリスト生成部を示すブロック図で
ある。

【図１０】アウトラインベクタの説明図である。

【図１１】曲線の再帰的な分割を示す説明図である。

【図１２】リストデータ生成部で生成されるディスプレ
イリスト（文字／図形の場合）の構造を示す図である。

【図１３】リストデータ生成部で生成されるディスプレ
イリスト（ラスタの場合）の構造を示す図である。

【図１４】ディスプレイリストのバンド境界での分割の
概要を示す説明図である。

【図１５】ディスプレイリストのバンド分割の処理の流
れを示すフローチャートである。

【図１６】ディスプレイリストバッファにおけるディス
プレイリストの記憶形態を示す説明図である。

【図１７】座標点生成ＬＳＩの構成を示すブロック図で
ある。

【図１８】座標点生成回路の回路構成を示すブロック図
である。

【図１９】エッジリストバッファの構成を示す図であ
る。

【図２０】座標点生成ＬＳＩにおける１オブジェクトの
座標点生成処理の流れを示すフローチャートである。

【図２１】セルの入力とレジスタ設定処理の流れを示す
フローチャートである。

【図２２】座標点生成と出力処理の流れを示すフローチ
ャートである。

【図２３】座標点出力処理の流れを示すフローチャート
である。

【図２４】ソート部における処理の流れを示すフローチ
ャートである。

【図２５】ソート部におけるソート方法を示す説明図で
ある。

【図２６】ソート部の構成例を示すブロック図である。

【図２７】ソート部の処理の流れを示すフローチャート
である。

【図２８】印刷画像データ変換ＬＳＩの構成を示すブロ
ック図である。

【図２９】第２の実施の形態での座標点生成ＬＳＩの構
成例を示すブロック図である。

【図３０】エッジデータ追加処理回路の構成例を示すブ
ロック図である。

【図３１】第２の実施の形態での座標点生成回路の回路
構成を示すブロック図である。

【図３２】部分ソート回路の回路構成を示すブロック図
である。

【図３３】第２の実施の形態でのエッジリストバッファ
の構成を示す図である。

【図３４】第２の実施の形態での座標点生成ＬＳＩの全
体の処理の流れを示すフローチャートである。

【図３５】第２の実施の形態での座標点生成ＬＳＩのｙ
リストの処理の流れを示すフローチャートである。

【図３６】第２の実施の形態での座標点生成ＬＳＩのセ
ルの処理の流れを示すフローチャートである。

【図３７】第２の実施の形態での座標点生成ＬＳＩの座
標点出力処理の流れを示すフローチャートである。

【図３８】第２の実施の形態での座標点生成ＬＳＩのエ
ッジデータ更新処理の流れを示すフローチャートであ
る。

【図３９】第２の実施の形態での座標点生成ＬＳＩのセ
ル追加判定処理の流れを示すフローチャートである。

【図４０】第２の実施の形態でのソート部におけるソー
ト方法の概念を示す説明図である。

【図４１】第２の実施の形態でのソート部の構成例を示
すブロック図である。

【図４２】第２の実施の形態でのソート部の処理の流れ
を示すフローチャートである。

【図４３】第３の実施の形態でのディスプレイリストの
連結セルの構成を示す図である。

【図４４】第３の実施の形態での座標点生成回路の構成
例を示すブロック図である。

【図４５】第３の実施の形態での座標点生成処理の様子
を示す説明図である。

【図４６】初期値計算部の構成例を示すブロック図であ
る。

【図４７】初期値計算部の処理の流れを示すフローチャ
ートである。

【図４８】座標点計算部の構成例を示すブロック図であ
る。

【図４９】輪郭情報からビットマップ展開のためのエッ
ジの座標点を生成するまでの流れを示す説明図である。

【図５０】エッジが交差する図形要素の例を示した図で
ある。

【符号の説明】 １ 印刷データ ２ 入力手段 ３ リスト生成手段 ４ 座標点生成手段 ５ ソート手段 ６ 変換手段 ７ 印刷出力手段 １０ 印刷データスプール部 １１ 印刷データ解釈部 １２ ディスプレイリスト生成部 １３ バンド分割部 １４ ラスタデータ処理部 １５ ラスタデータバッファ １６ ディスプレイリストバッファ １７ ディスプレイリストバンドバッファ １８ ディスプレイリスト管理部 １９ 座標点生成部 ２０ ソート部 ２１ エッジリストバッファ ２２ 印刷画像データ変換部 ２３ ラスタデータバンドバッファ ２４ 出力バッファ ２５ プリンタ装置制御部 ２６ プリンタ装置

───────────────────────────────────────────────────── フロントページの続き (72)発明者 小柳 雅彦 神奈川県足柄上郡中井町境430 グリーン テクなかい 富士ゼロックス株式会社内 (72)発明者 石川 宏 神奈川県足柄上郡中井町境430 グリーン テクなかい 富士ゼロックス株式会社内

Claims (37)

【特許請求の範囲】
1. 【請求項１】 文字または図形に関する描画命令を印刷
   画像データに変換して印刷出力する印刷処理装置におい
   て、 所定の描画命令で記述された少なくとも文字または図形
   のいずれかの描画オブジェクトを有する印刷データを入
   力する入力手段と、 前記入力手段に入力された前記印刷データから前記描画
   オブジェクトの輪郭を構成するエッジの始点および終点
   の情報を有したリストを前記描画オブジェクト毎に生成
   するリスト生成手段と、 前記リスト生成手段で生成された前記リストの前記始点
   および終点の情報から前記描画オブジェクトの前記エッ
   ジを表す座標点を順次生成する座標点生成手段と、 前記座標点生成手段で生成された前記座標点に順序を付
   けるソート手段と、 前記描画オブジェクトの印刷画像データを印刷出力する
   印刷出力手段と、 前記ソート手段で決定された順番の前記座標点を前記印
   刷出力手段で出力可能な印刷画像データに変換する変換
   手段と、 を備えていることを特徴とする印刷処理装置。
2. 【請求項２】 前記座標点生成手段は、複数の座標点生
   成装置で構成されることを特徴とする請求項１記載の印
   刷処理装置。
3. 【請求項３】 前記複数の座標点生成装置は、座標点生
   成装置の数と同数の前記座標点を一度に生成することを
   特徴とする請求項２記載の印刷処理装置。
4. 【請求項４】 前記座標点生成手段は、前記描画オブジ
   ェクトのすべてのエッジの座標点生成が終了するまで、
   前記リストの前記始点および終点情報から前記座標点を
   順次、繰り返し生成することを特徴とする請求項１記載
   の印刷処理装置。
5. 【請求項５】 前記ソート手段は、前記座標点生成手段
   で生成された前記座標点の順番を変更するものであるこ
   とを特徴とする請求項１記載の印刷処理装置。
6. 【請求項６】 前記ソート手段は、所定のプログラムを
   中央演算処理装置で実行することにより前記座標点の順
   序付けを行うことを特徴とする請求項１記載の印刷処理
   装置。
7. 【請求項７】 所定の描画命令で記述された少なくとも
   文字または図形のいずれかの描画オブジェクトを有する
   印刷データから生成される印刷画像データを、印刷出力
   装置の走査ライン毎に出力する印刷処理装置において、 前記描画オブジェクトの輪郭を構成するエッジのエッジ
   情報を前記エッジ毎に有したディスプレイリストを前記
   走査ライン毎に生成するディスプレイリスト生成手段
   と、 前記ディスプレイリスト生成手段で生成された前記ディ
   スプレイリストの前記エッジ情報を用いて前記描画オブ
   ジェクトの前記エッジを表す座標点を順次生成する座標
   点生成手段と、 前記描画オブジェクトのすべてのエッジについて前記座
   標点生成が終了するまで前記ディスプレイリストの前記
   エッジ情報を前記座標点生成手段に繰り返し転送する管
   理手段と、 前記座標点生成手段で生成された前記座標点に順序を付
   けるソート手段と、 前記ソート手段で決定された順番の前記座標点を用いて
   前記印刷データを前記印刷出力装置で出力可能な印刷画
   像データに変換する変換手段と、 を備えていることを特徴とする印刷処理装置。
8. 【請求項８】 前記座標点生成手段は、複数の座標点生
   成装置で構成されることを特徴とする請求項７記載の印
   刷処理装置。
9. 【請求項９】 前記複数の座標点生成装置は、座標点生
   成装置の数と同数の前記座標点を一度に生成することを
   特徴とする請求項８記載の印刷処理装置。
10. 【請求項１０】 前記ディスプレイリストは、オブジェ
    クト毎に、少なくともヘッダ情報と、前記オブジェクト
    の前記エッジ情報とを含むことを特徴とする請求項７記
    載の印刷処理装置。
11. 【請求項１１】 前記ヘッダ情報は、少なくとも前記オ
    ブジェクトの色データと、エッジ数と、次のオブジェク
    トへのポインタとを含むことを特徴とする請求項１０記
    載の印刷処理装置。
12. 【請求項１２】 前記エッジ情報は、少なくとも前記描
    画オブジェクトの輪郭を構成するエッジの始点、エッジ
    の傾き、および前記エッジと前記走査ラインとの交差数
    を含むことを特徴とする請求項１０記載の印刷処理装
    置。
13. 【請求項１３】 前記エッジ情報は、前記走査ラインの
    位置情報と、前記エッジの開始する座標点、傾きおよび
    前記交差数を一組とする複数のエッジデータと、各エッ
    ジデータを連結するための複数のポインタとを含むこと
    を特徴とする請求項１２記載の印刷処理装置。
14. 【請求項１４】 前記座標点生成手段は、前記座標点を
    生成する毎に、前記交差数を１ずつ減らすことを特徴と
    する請求項１２記載の印刷処理装置。
15. 【請求項１５】 前記管理手段は、前記座標点生成装置
    が待機状態にあることを検出する検出手段と、検出され
    た前記座標点生成装置へ前記ディスプレイリストの前記
    エッジ情報を転送する転送手段とを備えていることを特
    徴とする請求項８記載の印刷処理装置。
16. 【請求項１６】 前記転送手段は、前記座標点の生成に
    より特定のエッジの前記交差数が０になった前記座標点
    生成装置へ、前記ディスプレイリストの有する他の前記
    エッジのエッジ情報を転送することを特徴とする請求項
    １５記載の印刷処理装置。
17. 【請求項１７】 前記管理手段は、前記転送手段により
    前記ディスプレイリストの前記エッジ情報を転送した
    後、ディスプレイリストの前記ポインタを、次に転送す
    る前記エッジデータが格納されているポインタに更新す
    る機能を備えていることを特徴とする請求項１５記載の
    印刷処理装置。
18. 【請求項１８】 前記管理手段は、前記待機状態にある
    座標点生成装置に転送する前記他のエッジのエッジ情報
    に含まれる走査ライン位置情報と次に転送する前記エッ
    ジデータが格納されているポインタとを、前記走査ライ
    ン位置情報が示す走査ラインにおける座標点生成を開始
    するまで保持しておくことを特徴とする請求項１５また
    は１６記載の印刷処理装置。
19. 【請求項１９】 前記管理手段は、前記ディスプレイリ
    ストの複数の走査ライン位置情報と当該走査ラインの次
    に転送するエッジデータが格納されているポインタとを
    保持する手段を備えていることを特徴とする請求項１５
    または１６記載の印刷処理装置。
20. 【請求項２０】 前記座標点生成装置は、前記座標点を
    保持するための第１レジスタと、前記エッジの傾きを保
    持するための第２レジスタと、前記交差数を保持するた
    めの第３レジスタと、前記第１レジスタと第２レジスタ
    の内容を加算する第１の演算器と、前記第３レジスタの
    内容を１減算する第２の演算器とから構成されることを
    特徴とする請求項８記載の印刷処理装置。
21. 【請求項２１】 前記座標点生成装置は、前記ディスプ
    レイリストの前記エッジ情報を座標点生成装置内で使用
    される内部形式に変換する初期値計算部と、前記内部形
    式に変換されたエッジ情報を用いて前記エッジを表す座
    標点を順次生成する座標点計算部とから構成されること
    を特徴とする請求項８記載の印刷処理装置。
22. 【請求項２２】 前記内部形式は、前記座標点と、走査
    ライン毎の座標点の基本増分と、前記エッジと走査ライ
    ンとの交点と座標点との誤差と、走査ライン毎の誤差の
    増分を含むことを特徴とする請求項２１記載の印刷処理
    装置。
23. 【請求項２３】 前記内部形式の各構成要素は、すべて
    整数であることを特徴とする請求項２１記載の印刷処理
    装置。
24. 【請求項２４】 前記座標点計算部は、前記座標点を保
    持するための第１レジスタと、前記基本増分を保持する
    ための第２レジスタと、前記誤差を保持するための第３
    レジスタと、前記誤差が正の時に誤差に加えられる値を
    保持するための第４レジスタと、前記誤差が負の時に誤
    差に加えられる値を保持するための第５レジスタと、前
    記交差数を保持するための第６レジスタと、前記第１レ
    ジスタと第２レジスタとの内容を加算する第１の演算器
    と、前記第３レジスタと第４レジスタまたは第５レジス
    タとの内容を加算する第２の演算器と、前記第６レジス
    タの内容を１減算する第２の演算器とから構成されるこ
    とを特徴とする請求項２３記載の印刷処理装置。
25. 【請求項２５】 前記ソート手段は、前記座標点を入力
    する座標点入力手段と、前記座標点の中のある特定の値
    を選択する座標点値選択手段と、前記座標点値選択手段
    で選択された座標点と他の前記座標点との値の大小を判
    定する座標点判定手段と、前記座標点判定手段により判
    定された結果に従って前記座標点を振り分ける座標点分
    別手段と、前記座標点の順序付けがすべて終了するまで
    管理するソート管理手段とを備えていることを特徴とす
    る請求項７記載の印刷処理装置。
26. 【請求項２６】 前記変換手段で変換された１ページ分
    の印刷画像データを格納するためのページメモリ手段を
    備えていることを特徴とする請求項７記載の印刷処理装
    置。
27. 【請求項２７】 前記ディスプレイリスト生成手段で生
    成された前記ディスプレイリストの１ページ分を所定の
    バンド数で分割されるバンド単位で分割するバンド分割
    手段と、前記変換手段で変換された印刷画像データを前
    記バンド単位に格納するためのバンドメモリ手段とを備
    え、前記座標点生成手段は前記バンド分割手段で分割さ
    れた前記ディスプレイリストの前記エッジ情報を用いて
    前記描画オブジェクトの前記エッジを表す座標点を順次
    生成することを特徴とする請求項７記載の印刷処理装
    置。
28. 【請求項２８】 前記分割手段は、複数のバンドにまた
    がる前記描画オブジェクトについては、そのディスプレ
    イリストをバンドの境界で分割してそれぞれ１バンドに
    収まる複数のディスプレイリストにすることを特徴とす
    る請求項２７記載の印刷処理装置。
29. 【請求項２９】 少なくとも前記座標点生成手段と、前
    記管理手段と、前記ソート手段と、前記変換手段とは、
    一つの実装手段に一体に構成されていることを特徴とす
    る請求項７記載の印刷処理装置。
30. 【請求項３０】 前記実装手段は、ディスプレイリスト
    生成までの処理手段とは着脱可能であることを特徴とす
    る請求項２９記載の印刷処理装置。
31. 【請求項３１】 前記座標点生成手段は、前記ディスプ
    レイリスト生成手段で生成された前記ディスプレイリス
    トの前記エッジ情報を用いて前記描画オブジェクトの前
    記エッジを表す座標点を順次生成する複数の座標点生成
    装置と、前記複数の座標点生成装置と同数の前記座標点
    を一度に順序付けする部分ソート手段とを備えているこ
    とを特徴とする請求項７記載の印刷処理装置。
32. 【請求項３２】 前記複数の座標点生成装置の内、待機
    状態にある座標点生成装置は、待機状態でない座標点生
    成装置の出力する座標点の最大値以上の特定の値を前記
    部分ソート手段に出力することを特徴とする請求項３１
    記載の印刷処理装置。
33. 【請求項３３】 前記部分ソート手段は、少なくとも座
    標点を保持するための複数のレジスタと、二つの前記座
    標点の大小比較を行うための複数の２入力ソート回路
    と、前記複数の２入力ソート回路から出力される座標点
    と前記座標点生成装置から入力される座標点との前記レ
    ジスタ回路への入力を切り換えるための複数のマルチプ
    レクサとから構成されることを特徴とする請求項３１記
    載の印刷処理装置。
34. 【請求項３４】 前記管理手段は、ソートを必要とする
    走査ラインを前記ソート手段に通知することを特徴とす
    る請求項３１記載の印刷処理装置。
35. 【請求項３５】 前記ソート手段は、前記座標点を入力
    する座標点入力手段と、入力された前記座標点から前記
    部分ソート手段で順序付けされた座標点の組を選択する
    座標点部分選択手段と、前記座標点部分選択手段で選択
    された順序付けされた座標点の組と前記座標点部分選択
    手段で選択された別の順序付けされた座標点の組とのそ
    れぞれの座標点の値の大小を判定する座標点判定手段
    と、前記座標点判定手段により判定された結果に従って
    二つの前記座標点の組を併合する座標点併合手段と、前
    記座標点の順序付けがすべて終了するまで管理するソー
    ト管理手段とを備えていることを特徴とする請求項３１
    記載の印刷処理装置。
36. 【請求項３６】 文字または図形に関する描画命令を印
    刷画像データに変換して印刷出力する印刷処理方法にお
    いて、 所定の描画命令で記述された少なくとも文字または図形
    のいずれかの描画オブジェクトを有する印刷データを入
    力し、 前記描画オブジェクトの輪郭を構成するエッジの始点お
    よび終点の情報を有したリストを前記描画オブジェクト
    毎に生成し、 前記リストの前記始点および終点情報から前記描画オブ
    ジェクトの前記エッジを表す座標点を一度に複数生成
    し、 生成された前記座標点に順序を付け、 順序付け工程で決定された順番の前記座標点情報を最終
    的に印刷出力される画像データに変換する、 ことからなることを特徴とする印刷処理方法。
37. 【請求項３７】 所定の描画命令で記述された少なくと
    も文字または図形のいずれかの描画オブジェクトを有す
    る印刷データから生成される印刷画像データを、この印
    刷画像データを出力する印刷出力装置の走査ライン毎に
    出力する印刷処理方法において、 前記描画オブジェクトの輪郭を構成するエッジのエッジ
    情報を前記エッジ毎に有したディスプレイリストを前記
    走査ライン毎に生成し、 生成された前記ディスプレイリストの前記エッジ情報を
    用い、全ディスプレイリストについて前記描画オブジェ
    クトの前記エッジを表す座標点を生成し、 生成された前記座標点に順序付けをし、 順序付け工程で決定された順番の前記座標点情報を用い
    て前記印刷データを前記印刷出力装置で出力可能な印刷
    画像データに変換する、 ことからなることを特徴とする印刷処理方法。