JPH1049690A

JPH1049690A - 画像形成装置

Info

Publication number: JPH1049690A
Application number: JP8208016A
Authority: JP
Inventors: Shoji Sakamoto; 彰司坂本; Masao Morita; 雅夫森田
Original assignee: Fuji Xerox Co Ltd
Current assignee: Fujifilm Business Innovation Corp
Priority date: 1996-08-07
Filing date: 1996-08-07
Publication date: 1998-02-20

Abstract

(57)【要約】【課題】必要なメモリ量が少なく、データ転送の負荷
が小さな画像形成装置を提供することを目的とする。【解決手段】入力された画像描画命令は描画図形記述
生成手段１で解釈実行されて図形を特定するための識別
子、重なりの優先順位の情報が追加された描画図形記述
が生成される。この描画図形記述は図形記述保持手段２
に登録されると同時に、記述更新手段３がそれまでに登
録されている描画図形記述との描画領域の干渉関係を調
べ、他の描画図形との重なり関係で隠れてしまう描画図
形については重なりの優先度が低い方の描画図形の要素
図形記述に、重なる要素図形を特定する識別子と交点座
標とからなる交点情報を加え、その交点情報から交点情
報の最適化を行う。その描画図形記述はベクトルデータ
生成手段４にてベクトル化され、出力処理手段５にて印
字可能な形式の出力データにする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は画像形成装置に関
し、特に文書を表現する言語で記述された命令列を実行
して画像情報を形成する際に画像を構成する図形間の重
なりの記述を最適化する画像形成装置に関する。

【０００２】

【従来の技術】文書を表現するページ記述言語のプログ
ラムはプリンタによって逐次的に解釈実行され、ページ
の終端を示す命令が実行されると実際の印字が行われ
る。このためプリンタは少なくとも１ページ分の画像を
保持するバッファを備え、このバッファ上で描画命令を
実行し、印刷可能な画像データを構成している。

【０００３】従来のこのような構成では、出力装置の解
像度が増すにつれて、印刷データの量が増大し、バッフ
ァ容量の増大によるシステム全体の高コスト化とシステ
ム内でのデータ転送量の増大による速度低下とを招いて
いる。また、ページの構成要素の展開および重ね合せの
処理はデータ量の大きな印刷可能画像データのレベルで
行われているので、画像形成装置の処理負荷も大きくな
ってきている。

【０００４】これに対して、ページ記述言語の画像描画
命令に優先順位を与え、ある描画命令の展開の際に、そ
の命令よりも優先順位の高い命令で既に展開した画素に
は上書きをしないことで展開処理の効率化を図る方法が
特開平６−１１９４５６号公報に提案されている。この
展開処理方法では、重なりを検出する方法を画素の参照
によって行っているため、画像データ形式の容量の大き
なバッファを保持する必要がある。

【０００５】また、重ね合せの処理の別の形態として、
オーバレイ処理などを用いて共通の原稿に一部のデータ
だけが異なる複数の原稿を重ね合わせて印刷する差し込
み印刷がある。この差し込み印刷では、先に作成された
ページデータを保存しておき、これに変更箇所に相当す
るデータを合成して印刷データを作成する処理が行われ
る。この合成処理を印刷可能画像データのレベルで行う
場合には、同じように大量のメモリと高速な演算装置と
が必要となる。

【０００６】これを避けるためには、合成処理を工夫す
る必要がある。特開平４−２５０５８２号公報や特開平
４−２８２７８４号公報に提案されている方法は、ペー
ジを構成するスキャンライン上での図形の重なり処理を
効率的に行うものであるが、スキャンラインを仮定して
いるため画素形式のページデータしか出力することがで
きず、この出力にオーバレイ処理などを適用する際に
は、やはり大量のメモリと高速な演算装置とが必要とな
る。

【０００７】いずれにしても、従来の重ね合せの処理で
は、図形の重ね合せの結果はデータ量の大きな印刷可能
画像データのレベルで表現されている。これに対処する
ためには、印刷可能画像データよりも抽象度の高い図形
記述のレベルで図形の重なりが適切に表現されているこ
とが必要であり、かつ、抽象度の高い図形記述のレベル
で表現された図形記述の重なりを処理する機構が必要と
なる。

【０００８】このような図形記述の重なりを処理する場
合、小さな図形が大きな図形によって完全に隠されてし
まうときにその小さな図形を消したり（縮退）、第１の
図形が第２の図形を横切るように重なるときに第１の図
形を分割するが、重なりに応じて図形記述を縮退または
分割するためには、縮退あるいは分割の処理後の図形記
述が図形の重なりの境界を正確に保持している必要があ
る。さもなければ、誤差による交点や境界付近での画素
の抜けや不正な重なりの原因になる。このためには、特
開平４−２２２０６０号公報に提案されているような反
復計算を用いた正確な交点の算出が必要となる。

【０００９】

【発明が解決しようとする課題】このように、従来の画
像形成装置では、複数の図形の描画領域の干渉によって
発生する重なりが図形間の関係として適切に表現および
処理されていないために、図形記述の重なりを個々に独
立した記述に対して最適化しようとしたり、スキャンラ
イン上の画素の色の変化点を求める問題に還元しようと
する際に、大容量のメモリが要求され、その上でデータ
転送をするのでデータ転送の負荷も大きく、正確な交点
の算出のためにシステムの計算負荷が増大するという問
題点があった。これを解決するには、重なり関係を表現
できる図形記述とその処理方法を確立することが必要と
なる。このとき、干渉する図形の重なりの位置を特定す
るためには互いの図形の内部構造を参照する必要がある
が、重なり処理によって図形記述が縮退または分割され
ると正確な参照を行うことができない点にも注意しなけ
ればならない。

【００１０】本発明はこのような点に鑑みてなされたも
のであり、画像形成のために必要なメモリ量が少なく、
データ転送の負荷が小さな画像形成装置を提供すること
を目的とする。

【００１１】

【課題を解決するための手段】本発明では上記問題を解
決するために、ページ記述言語で記述された画像描画命
令を実行して出力画像を得るための画像形成装置におい
て、入力された前記画像描画命令を解釈して描画図形の
外形を表す有向直線分および有向曲線分の列、描画図形
識別子、および重なり優先度から成る描画図形記述を生
成する描画図形記述生成手段と、前記描画図形記述生成
手段で生成された描画図形記述を保持する図形記述保持
手段と、前記図形記述保持手段が保持する描画図形記述
の重なり関係に基づいて描画図形記述に重なり情報を付
加するように前記描画図形記述を更新する記述更新手段
と、前記図形記述保持手段に保持された描画図形記述か
らベクトル記述を生成するベクトル記述生成手段と、前
記ベクトル記述生成手段によって生成されたベクトル記
述を用いて印字可能な形式の出力データを生成する出力
処理手段とを備えていることを特徴とする画像形成装置
が提供される。

【００１２】このような画像形成装置によれば、描画図
形記述生成手段によって生成され図形記述保持手段に保
持された描画図形記述を構成する線分や曲線などの描画
図形記述に、その描画図形と重なる別の描画図形を特定
するための識別子と交点の座標との重なり情報を記述更
新手段が付加するようにした。この重なり情報を用いて
画素レベルでの交点や境界を決定することで、すなわ
ち、データ量の大きな画像データのレベルでなく、より
抽象度の高いレベルの描画図形記述で、重なり処理をす
ることにより、バッファの容量の増大を抑えるととも
に、誤差による交点や境界付近での画素の抜けや不正な
重なりが避けられる。また、こうして生成された描画図
形記述を用いることにより、オーバレイ処理などの際
に、プリンタシステムのメモリ使用量とデータ転送の負
荷を抑えることができる。

【００１３】また、本発明によれば、ページ記述言語で
記述された画像描画命令を実行して出力画像を得るため
の画像形成装置において、入力された前記画像描画命令
を解釈して描画図形の外形を表す有向直線分および有向
曲線分の列、描画図形識別子、および重なり優先度から
成る描画図形記述を生成する描画図形記述生成手段と、
前記描画図形記述生成手段で生成された描画図形記述か
らベクトル記述を生成するベクトル記述生成手段と、前
記ベクトル記述生成手段で生成されたベクトル記述を保
持するベクトル記述保持手段と、前記ベクトル記述保持
手段が保持するベクトル記述の重なり関係に基づいてベ
クトル記述に重なり情報を付加するように前記ベクトル
記述を更新する記述更新手段と、前記ベクトル記述保持
手段によって保持されたベクトル記述を用いて印字可能
な形式の出力データを生成する出力処理手段とを備えて
いることを特徴とする画像形成装置が提供される。

【００１４】上記構成によれば、描画図形記述生成手段
によって描画図形記述が生成され、さらにベクトル記述
生成手段でベクトル記述が生成された後、ベクトル記述
保持手段に保持されたベクトル記述を構成する要素ベク
トルの記述に、その要素ベクトルと交差する他の要素ベ
クトルを特定するための識別子と交点の座標との重なり
情報を記述更新手段が付加するようにした。この重なり
情報を用いて画素レベルでの交点や境界を決定すること
で、すなわち、データ量の大きな画像データのレベルで
なく、より抽象度の高いレベルのベクトル記述で、重な
り処理をすることにより、バッファの容量の増大を抑え
るとともに、誤差による交点や境界付近での画素の抜け
や不正な重なりが避けられる。また、こうして生成され
た図形記述を用いることにより、オーバレイ処理などの
際に、プリンタシステムのメモリ使用量とデータ転送の
負荷を抑えることができる。

【００１５】

【発明の実施の形態】以下、本発明の実施の形態を図面
を参照して説明する。図１は第１の発明の原理構成を示
す図である。本発明の画像形成装置は、画像描画命令を
受ける描画図形記述生成手段１と、この描画図形記述生
成手段１で生成された描画図形記述を保持する図形記述
保持手段２と、この図形記述保持手段２が保持する描画
図形記述に対して重なり関係に基づいた更新処理をする
記述更新手段３と、図形記述保持手段２の描画図形記述
からベクトル記述を生成するベクトル記述生成手段４
と、このベクトル記述生成手段のベクトル記述から画素
レベルの出力データを出力する出力処理手段５と、図形
記述保持手段２の描画図形記述を退避し、かつ、退避さ
れた描画図形記述を図形記述保持手段２に出力する二次
記憶手段６とを備えている。

【００１６】この構成において、ページ記述言語で記述
された画像描画命令の入力は、描画図形記述生成手段１
によって解釈実行され、描画図形を表す描画図形記述が
生成される。この描画図形記述には、図形を特定するた
めの識別子、重なりの優先順位および図形を構成する線
分や点などの要素図形の情報が含まれている。

【００１７】描画図形記述生成手段１で生成された描画
図形記述は図形記述保持手段２に送られる。図形記述保
持手段２では、新たな記述を登録すると同時に、記述更
新手段３がそれまでに登録されている描画図形記述との
描画領域の干渉関係を調べる。この結果、互いに干渉す
る描画図形の間で重なりの優先度が低くて他の描画図形
との重なり関係で下になってしまう描画図形について
は、記述更新手段３がその描画図形を構成する有向直線
分または有向曲線分のそれぞれの要素図形記述につい
て、その要素図形と重なる要素図形を特定するための描
画図形および要素図形の識別子と交点の座標とを加え
る。

【００１８】こうして得られた交点記述に対しては、記
述更新手段３により、まず、要素図形の向きを考慮した
整列が行われる。これは、要素図形の端点の座標値から
それぞれの座標軸方向での増減を調べ、それを基に昇順
あるいは降順のいずれで整列するかを決め、この順に辞
書式の整列を行う。次に、記述更新手段３は、一つの要
素図形記述に現れる複数の交点記述のうち同一描画図形
との複数の交点記述の内部にあり、その描画図形よりも
重なり優先度の低い描画図形との交点記述を削除するこ
とで、交点記述の最適化を行う。上述の動作をページの
終端を表す命令を検出するまで繰り返すことで、図形記
述保持手段２には重なりの情報を含む１ページ分の描画
図形記述が生成される。

【００１９】こうして生成された描画図形記述は、ベク
トルデータ生成手段４によってベクトルデータに変換さ
れる。このベクトルデータは交点記述を反映しており、
他の描画図形との重なりの下になる部分についての情報
を含まない。

【００２０】このベクトルデータは出力処理手段５に送
られて出力処理され、印字可能な形式の出力データを出
力する。ベクトルデータを用いて出力処理を行う場合、
画素情報レベルでの重ね合せの処理を行う必要がないた
め、扱うデータ量を抑えることができる。

【００２１】また、オーバレイ処理などを行う際には、
図形記述保持手段２で生成された重なりの情報を含む１
ページ分の描画図形記述は二次記憶手段６に一旦退避さ
れる。ここで、新たな画像描画命令が入力されるときに
は、まず、二次記憶手段６に退避された描画図形記述が
図形記述保持手段２に読み込まれる。この読み込まれた
描画図形記述が新たな画像描画命令による描画図形記述
との重なり処理の初期値となる。この場合も、画素情報
レベルでの重ね合せの処理を行う必要がないため、扱う
データ量を抑えることができる。

【００２２】図２は第２の発明の原理構成を示す図であ
る。図示の画像形成装置は、画像描画命令を受ける描画
図形記述生成手段１１と、この描画図形記述生成手段１
１で生成された描画図形記述からベクトル記述を生成す
るベクトル記述生成手段１２と、このベクトル記述生成
手段１２で生成されたベクトル記述を保持するベクトル
記述保持手段１３と、このベクトル記述保持手段１３が
保持するベクトル記述に対して重なり関係に基づいた更
新処理をする記述更新手段１４と、ベクトル記述保持手
段１３のベクトル記述から画素レベルの出力データを出
力する出力処理手段１５と、ベクトル記述保持手段１３
のベクトル記述を退避し、かつ、退避されたベクトル記
述をベクトル記述保持手段１３に出力する二次記憶手段
１６とを備えている。

【００２３】この構成によれば、入力された画像描画命
令は、描画図形記述生成手段１１によって解釈実行さ
れ、図形を特定するための識別子、重なりの優先順位お
よび図形を構成する線分や点などの要素図形の情報を含
む描画図形記述が生成される。この描画図形記述生成手
段１１で生成された描画図形記述は直ちにベクトル記述
生成手段１２に送られてベクトル化の処理が施される。

【００２４】次いで、ベクトル記述生成手段１２で生成
されたベクトル記述はベクトル記述保持手段１３にて保
持される。このベクトル記述保持手段１３に保持された
ベクトル記述に対して、記述更新手段１４は描画図形ベ
クトルを構成する要素ベクトルの記述に、この要素ベク
トルと交差する他の要素ベクトルを特定する識別子と交
点の座標とを重なり情報として付加する。また、記述更
新手段１４は描画図形ベクトルを構成する要素ベクトル
の記述に現れる交点をその要素ベクトルの向きに従って
整列し、整列された交点のうち重なり優先度の高い図形
との交点の内部にあって、その図形よりも重なり優先度
の低い図形との交点を削除することにより重なり情報の
最適化を行う。上述の動作をページの終端を表す命令を
検出するまで繰り返すことで、ベクトル記述保持手段１
３には重なりの情報を含む１ページ分のベクトル記述が
生成される。

【００２５】このようにして処理されたベクトル記述
は、出力処理手段１５に送られて出力処理され、印字可
能な形式の出力データを出力する。このように、ベクト
ル記述をベクトル記述保持手段１３に保存し、このベク
トル記述保持手段１３上で重ね合せの処理を行うことに
より、重ね合せの処理において自由曲線などを表す曲線
分を扱うことを避け、計算量を抑えることができる。

【００２６】また、こうして生成されたベクトル記述を
二次記憶手段１６に退避しておき、別の入力から生成さ
れたベクトル記述と重ね合せの処理を行うことで、大量
のメモリを使用することなくオーバレイ処理を実現する
ことができる。

【００２７】次に、第１の発明の実施の形態を、ネット
ワークに接続された印刷システムに適用した場合を例に
して説明する。図３は本発明による画像形成装置を適用
したネットワーク印刷システムの構成例を示す図であ
る。ネットワーク印刷システムは、複数のクライアント
計算機２１，２２，２３，・・・と、ネットワーク３０
と、プリントサーバ４０と、プリントエンジン５０とか
ら構成され、本発明による画像形成装置はプリントサー
バ４０の一部として適用されている。プリントサーバ４
０は、ネットワーク３０に接続された命令解析部４１
と、図形記述更新部４２と、量子化部４３と、ページバ
ッファ４４と、出力処理部４５とが共有バス４６によっ
て相互に接続されている。プリントサーバ４０は、ま
た、出力処理部４５に接続されたプリンタインタフェー
ス４７を備え、このプリンタインタフェース４７の出力
はプリントエンジン５０に接続されている。

【００２８】ネットワーク印刷システムにおいて、クラ
イアント計算機２１，２２，２３，・・・で作成された
印刷ジョブはネットワーク３０を介してプリントサーバ
４０の命令解析部４１に送られる。命令解析部４１で
は、受け取った印刷ジョブの内容をページ記述言語の命
令列として解釈実行し、個々の描画図形を表す図形記述
を生成する。生成された図形記述はページバッファ４４
に保存される。このとき、既にページバッファ４４に保
存されている図形と新たに生成された図形との間に重な
りがある場合には、重なりの優先度に基づいて図形記述
更新部４２によって図形記述が更新される。ページの終
端を示す命令が検出されると、ページバッファ４４に保
存されている図形記述は、量子化部４３に送られてベク
トル化される。量子化部４３の出力であるベクトルデー
タは、出力処理部４５に送られ、ここで印字可能な形式
の出力データが生成される。出力処理部４５の出力であ
る出力データは、プリンタインターフェース４７を介し
てプリントエンジン５０に送られ、印刷される。

【００２９】命令解析部４１は、入力として与えられた
ページ記述言語の命令列を順に解釈実行し、対応する図
形記述を生成する。この図形記述には、図形を構成する
個々の要素図形の記述に加え、与えられたページ記述言
語に記述されていない情報として、図形を識別するため
の識別子と重なりの優先度とが含まれている。要素図形
の記述には、その要素図形を定義するために必要な特徴
点の座標が含まれている。たとえば、線分の記述には両
端点の座標が含まれており、曲線の記述には両端点と２
つの制御点の４点の座標が含まれている。なお、本実施
の形態においては、図形記述における要素図形の記述
は、反時計回りの順に連続して現れるものとする。ある
要素図形の記述は、その要素図形を含む図形記述に与え
られた識別子と図形記述中の出現順序とによって特定す
ることができる。

【００３０】命令解析部４１によって生成された図形記
述は、順にページバッファ４４に保存される。ここで、
第１の図形記述を新たにページバッファ４４に登録する
際に、その第１の図形記述が表現する図形が既に登録さ
れた第２の図形記述の表現する図形と重なる場合には、
図形記述更新部４２によってそれらの図形記述の間で重
なり優先度の低い第２の図形記述に対して重なり情報が
付加される。この処理の流れを以下に示す。

【００３１】図４は重なり判定手続きの処理の流れを示
すフローチャートである。ここでは、重なり判定を図形
の外接矩形を用いた場合を例にして説明する。そして、
二つの図形の外接矩形を数値の四つ組で表すものとし、
それぞれの数値はその矩形の左上の点と右下の点とのｘ
座標およびｙ座標の値を表すものとする。

【００３２】したがって、最初に、二つの外接矩形の左
上の点のｘ座標およびｙ座標の最大値を変数Ｌｘ，Ｌｙ
および右下の点のｘ座標およびｙ座標の最小値を変数Ｈ
ｘ，Ｈｙにそれぞれセットする（ステップＳ１）。続い
て、二つの外接矩形のｘ座標およびｙ座標に関する変数
の比較を行う（ステップＳ２）。すなわち、Ｌｘ＜Ｈｘ
であり、かつＬｙ＜Ｈｙであるか否かを判定し、両方を
満足するならば、重なりありと判定して終了する。ま
た、両方の比較を満足しなければ、重なりなしと判定し
て終了する。

【００３３】この重なりの有無の判定は、二つの外接矩
形が与えられた場合に、以下の理由によって可能にな
る。矩形領域のある軸への正射影を考えると、これは幅
を持った値の範囲を形成する。二つの範囲が重なる場合
は、重なり領域の端は、二つの範囲の左側境界のうち右
側にあるものと右側境界のうち左側にあるものとであ
り、これらが左から右へこの順に現れる。二つの範囲が
重ならない場合には、これらの出現順序が逆になる。図
４の重なり判定手続きはこのような性質を利用してい
る。

【００３４】次に、このような重なり判定の結果に基づ
く図形記述更新部の次の処理について説明する。図５は
重なり情報の付加処理の流れを示すフローチャートであ
る。まず、重なり判定の結果が重なりありであったかど
うかが判定される（ステップＳ１１）。ここで、重なり
がないと判定されると、この処理はそのまま終了し、重
なりがあると判定されると、新たに登録される第１の図
形と干渉する既登録の第２の図形を特定する（ステップ
Ｓ１２）。次に、第１の図形を構成する要素図形のそれ
ぞれに対してその要素図形と重なる第２の図形の要素図
形を特定し（ステップＳ１３）、要素図形間の交点を計
算し、第２図形を構成する要素図形記述に第１の図形の
要素図形を特定する情報と交点の座標とを含む重なり情
報を付加する（ステップＳ１４）。このとき、交点の座
標については、厳密な値を求める必要はなく、たとえ
ば、制御点を結んだ線分で曲線分を近似しても構わな
い。

【００３５】上述の動作をページの終端を表す命令を検
出するまで繰り返していき、１ページ分の図形記述がペ
ージバッファ４４に生成されると、次に、ページバッフ
ァ４４に蓄積された図形記述に含まれる重なり情報の最
適化を行う。これは、交点情報に対する二つの操作から
成る処理である。まず、それぞれの要素図形記述に付加
された交点記述をその交点の座標値を用いて整列する。
整列は２軸方向への座標値を用いて辞書順に行われ、要
素図形のそれぞれの軸方向への増加あるいは減少が昇順
あるいは降順の整列に対応する。この手続きのフローチ
ャートを図６および図７に示す。

【００３６】図６は整列処理の流れの例を示すフローチ
ャートである。まず、蓄積された図形記述に含まれる重
なり情報の有無が判定される（ステップＳ２１）。ここ
で、重なり情報がないと判定されると、この処理はその
まま終了し、重なり情報があると判定されると、要素図
形記述を構成する頂点の座標値のうち、まず、ｘ座標に
関して頂点の座標値がｘ軸方向に増加しているか否かを
判定し（ステップＳ２２）、ｘ軸方向に増加している場
合は、要素図形記述に付加された交点記述の交点を昇順
に整列し（ステップＳ２３）、ｘ軸方向に減少している
場合は、交点を降順に整列する（ステップＳ２４）。次
に、ｙ座標に関して交点の座標値がｙ軸方向に増加して
いるか否かを判定し（ステップＳ２５）、ｙ軸方向に増
加している場合は、昇順に整列し（ステップＳ２６）、
ｙ軸方向に減少している場合は、降順に整列する（ステ
ップＳ２７）。そして、２軸方向への座標値を用いて辞
書順に整列が行われる（ステップＳ２８）。以上の処理
により、線分の向きに沿って始点から終点に向かって交
点が並ぶように整列されることになる。

【００３７】次に他の図形との重なりの下になる交点情
報を調べ削除する。これは、それぞれの要素図形に付加
された重なり情報のうち、重なり優先度ｒ１を持つ図形
との交点がｒ１よりも高い優先度ｒ２を持つ図形との交
点に挟まれている場合に、前者は後者との重なりの下に
隠されてしまっているものと考え、これを削除すること
で実現される。この手続きのフローチャートを図７に示
す。

【００３８】図７は最適化処理の流れを示すフローチャ
ートである。ここでは、交点情報が整列された状態で受
け取られる。まず、整列された交点情報に対して重なり
情報の有無が判定される（ステップＳ３１）。ここで、
重なり情報がないと判定されると、この処理はそのまま
終了し、重なり情報があると判定されると、優先度の変
数ｐｒｉｏの値を０に初期化する（ステップＳ３２）。
次に、交点の情報を記述された順に走査するが、ここ
で、全ての交点情報を走査したか否かを判定する（ステ
ップＳ３３）。全ての交点情報を走査した場合には、そ
のまま終了する。全ての交点情報を走査していない場合
には、次の交点の情報（最初は先頭の交点の情報）を走
査する（ステップＳ３４）。その交点の重なり優先度を
調べて、今、注目している交点の重なり優先度を別の変
数ｐに代入する（ステップＳ３５）。次に、この変数ｐ
と変数ｐｒｉｏとを比較する（ステップＳ３６）。ここ
で、注目している現在の交点の重なり優先度が比較対象
の交点の重なり優先度よりも高ければ、現在の交点を削
除することはできないので、変数ｐｒｉｏに変数ｐを代
入して（ステップＳ３７）、ステップＳ３３に戻り、次
の交点へ進む。現在の交点の重なり優先度が比較対象の
交点の重なり優先度よりも高くなければ、現在の交点が
重なりによって隠れてしまって本来は出てこないはずの
交点であると判定し、重なり優先度の低い現在の交点を
退避しておく（ステップＳ３８）。次に、変数ｐと変数
ｐｒｉｏとが等しいかどうかが判定され（ステップＳ３
９）、等しくない場合には、ステップＳ３３に戻って、
削除可能な交点に関して調べていくことになる。優先度
が等しい場合には、今まで退避していた交点をまとめて
削除し（ステップＳ４０）、ステップＳ３２に戻って、
次の削除可能な交点群の探索に進む。

【００３９】以上の処理は、非常に単純なアルゴリズム
に因っているが、実際には交点が図形の中であるか外で
あるかが問題になり、図形の外であればその交点を削除
することはできない。したがって、最適化処理をより厳
密に行うには、それぞれの交点位置において干渉する要
素図形の交差の向きを交点情報に加え、これに非零巻数
規則や奇偶巻数規則を適用することで、正確な内外判定
を行い、重なり優先度の高い図形の内部にその図形より
も重なり優先度の低い図形との交点がある場合にはこれ
を取り除くことで実現される。この手続きのフローチャ
ートを図８に示す。ただし、巻数規則を用いた内部性判
定については、通常のページ記述言語の処理装置に実装
されているので、その詳細は省略する。

【００４０】図８は別の最適化処理の流れを示すフロー
チャートである。まず、整列された交点情報に対して重
なり情報の有無が判定される（ステップＳ５１）。ここ
で、重なり情報がないと判定されると、この処理はその
まま終了し、重なり情報があると判定されると、優先度
の変数ｐｒｉｏの値を０に初期化する（ステップＳ５
２）。次に、全ての交点情報を走査したか否かが判定さ
れる（ステップＳ５３）。全ての交点情報を走査した場
合には、そのまま終了し、全ての交点情報を走査してい
ない場合には、次の交点の情報を走査する（ステップＳ
５４）。その交点の重なり優先度を調べて、現在の交点
の重なり優先度を別の変数ｐに代入する（ステップＳ５
５）。次に、この変数ｐと変数ｐｒｉｏとを比較し（ス
テップＳ５６）、現在の交点の重なり優先度が比較対象
の交点の重なり優先度よりも高ければ、変数ｐｒｉｏに
変数ｐを代入して（ステップＳ５７）、ステップＳ５３
に戻る。現在の交点の重なり優先度が比較対象の交点の
重なり優先度よりも高くなければ、その交点について内
部性判定を行う（ステップＳ５８）。この内部性判定に
て、内部ではない場合、すなわち、現在の交点が図形の
外に出ていく境界である場合には、下に来る図形は残さ
なければいけないので、変数ｐｒｉｏを０に初期化し
（ステップＳ５９）、ステップＳ５３に戻る。内部性判
定により、現在の交点が図形の内側である場合には、現
在の交点を退避する（ステップＳ６０）。次に、変数ｐ
と変数ｐｒｉｏとが等しいかどうかが判定され（ステッ
プＳ６１）、等しくない場合には、ステップＳ５３に戻
る。優先度が等しい場合には、退避された交点を削除し
（ステップＳ６２）、ステップＳ５２に戻る。

【００４１】続いて、ページバッファ４４に含まれる図
形記述を量子化部４３によってベクトル化する。これは
曲線を微小線分で近似する処理と図形を構成する要素図
形の端点を確定する処理とから成る。曲線の微小線分に
よる近似は、曲線のモデルによって様々な方法がある
が、たとえばベジエ（Ｂｅｚｉｅｒ）曲線のモデルにお
いては曲線を分割してその端点を結ぶ線分と曲線との距
離が予め定めた範囲の値になるまで再帰的に分割を繰り
返すことで近似微小線分の系列を得る。曲線の微小線分
による近似が完了すると、図形を構成する要素図形は全
て線分に還元され、これによって、全ての交点の計算は
直線の交点を求める問題となり、反復計算を行うことな
く容易に正確な交点の座標を求めることができる。こう
して求めた交点の座標を用いて、要素図形記述をベクト
ルに分割する。分割後のベクトルは図形の重なりを反映
しており、図形の境界が他の図形の境界と交わる位置で
分割されている。

【００４２】上述の処理によって得られたベクトルデー
タは、出力処理部４５によって印刷可能なラスタの画素
形式に変換される。画素形式の出力データを得る場合に
は、ある走査線と交わるベクトルとの交点を求め、ある
交点から次の交点までを図形の色属性が示す適切な色で
塗りつぶせばよい。

【００４３】以上の手続きを具体的な図形記述に適用し
た例を示す。図９は描画図形および対応するページ記述
言語入力および図形記述を示す図である。図９の（Ａ）
は描画される三角形の図形６０と、この図形６０を表す
ページ記述言語入力６１と、このページ記述言語入力６
１から生成された図形記述６２とを示しており、図９の
（Ｂ）は描画される扇形の図形７０と、この図形７０を
表すページ記述言語入力７１と、このページ記述言語入
力７１から生成された図形記述７２とを示している。

【００４４】すなわち、命令解析部４１に図形６０，７
０を表すページ記述言語入力６１，７１が与えられる
と、命令解析部４１では、図形記述６２，７２がそれぞ
れ生成される。このとき、それぞれの図形記述６２，７
２には、ページ記述言語入力６１，７１に含まれていな
い情報である、図形を一意に特定するための識別子と重
なりの優先順位を表す重なり優先度とが付加される。図
示の例によれば、図形記述６２には、入力の順に与えら
れた識別子ｉｄ＜１＞および同じく入力の順に与えられ
た重なり優先度ｐｒｉｏｒｉｔｙ＜１＞が付加され、図
形記述７２には、識別子ｉｄ＜２＞および重なり優先度
ｐｒｉｏｒｉｔｙ＜２＞が新たに付加されている。

【００４５】こうして生成された図形記述６２，７２は
順にページバッファ４４へと送られる。ページバッファ
４４では、新たな図形記述を登録する際には、その図形
記述が表す図形の描画領域と既に登録された図形記述が
表す図形の描画領域とが重なるかどうかを調べ、重なり
がある場合には重なりの下になる図形記述に重なり情報
を付加する処理がなされる。

【００４６】ページバッファ４４に図形記述６２が登録
され、次に、図形記述７２が登録される際には、重なり
判定が行われる。この重なり判定は、図４に示した図形
の外接矩形を用いて行われる。この例では、図形６０に
図形７０が重なるので、重なり判定によって重なりが検
出される。重なりが検出されると、各図形記述に含まれ
る要素図形記述相互の重なりが調べられ、重なり優先度
の低い図形記述の要素図形記述に交点情報が付加され
る。この様子を図１０に示す。

【００４７】図１０は重なり検出時の交点情報を付加す
る処理の説明図である。図１０の（Ａ）は図形６０，７
０の重なり状態を示している。図形６０は三つの要素図
形６０ａ，６０ｂ，６０ｃから構成され、図形７０は要
素図形７０ａ，７０ｂ，７０ｃから構成される。曲線分
の要素図形７０ａは両端点と二つの制御点とによって表
現されている。二つの図形６０，７０の要素図形が重な
っている交点は小さい四つの丸によって表している。図
１０の（Ｂ）は重なり情報が付加された図形記述を示し
ている。図示の例によれば、重なりが検出されることに
より、図形記述７２に含まれる要素図形記述のそれぞれ
に対して図形記述６２に含まれる要素図形記述が表す要
素図形との重なりを調べ、重なり優先度の低い図形記述
６２の要素図形記述に交点情報が付加され、図形記述６
２ａとなる。すなわち、２番目の要素図形記述に交点情
報（２，２，２５０，３００）および（２，３，３０
０，３００）が、３番目の要素図形記述に交点情報
（２，３，３００，２００）および（２，１，２５０，
１５０）が付加されている。これらの交点情報には、こ
の要素図形と重なる要素図形を特定するための図形の識
別子と、要素図形記述の図形記述中での出現順序、およ
び交点の座標とがこの順に含まれている。たとえば、交
点情報（２，２，２５０，３００）は、識別子ｉｄ＝２
の図形の２番目の要素図形と（２５０，３００）の位置
で重なっている、ことを示している。

【００４８】図１１は新たな図形が追加されたときの重
なり検出状態を示す図、図１２は図形記述に交点情報を
付加して最適化する処理の説明図である。図１１によれ
ば、図形６０の上に図形７０が重なっている状態で、さ
らに新たに平行四辺形の図形８０が図形６０，７０の一
部に重なるように追加して描画される状態を示してい
る。そして、重なり検出の結果、互いに重なり合う要素
図形の位置には交点情報を表す小さな丸が付加されてい
る。

【００４９】この図１１の重なり状態の各図形に対応す
る図形記述を図１２に示してある。図形６０の図形記述
６２ｂによれば、図１０に示した図形記述６２ａよりも
さらに新たな交点情報が付加されている。すなわち、２
番目の要素図形記述に交点情報（３，１，２２５，３０
０）および（３，３，２７５，３００）が、３番目の要
素図形記述に交点情報（３，３，３３７．５，２３７．
５）および（３，１，３１２．５，２１２．５）が付加
されている。また、図形７０の図形記述７２ａでは、二
つの直線線分の要素図形記述に新たな交点情報が付加さ
れている。すなわち、２番目の要素図形記述に交点情報
（３，１，２３７．５，３８７．５）および（３，３，
２６２．５，３１２．５）が、３番目の要素図形記述に
交点情報（３，３，３００，２５０）および（３，１，
３００，２２５）が付加されている。そして、図１２に
は図形８０に対応する図形記述８２が示されている。

【００５０】以上のようにして、図形記述に付加された
交点情報が蓄積され、ページの終端を表す命令が検出さ
れると、次に、重なり記述の最適化が行われる。この例
では、図形記述６２ｂに対して最適化がなされて、図形
記述６２ｃとなる。この図形記述６２ｃによれば、図形
記述６２ｂに比べて２番目の要素図形記述の中の交点情
報（２，２，２５０，３００）が削除されている。すな
わち、図形６０の第２辺に現れる交点のうち図形７０の
第２辺との交点は、図形７０よりも重なり優先度の高い
図形８０の第１辺との交点と図形８０の第３辺との交点
とに挟まれており、図形記述更新部４２によって最適化
されて取り除かれる。

【００５１】次いで、最適化された図形記述は量子化部
４３に渡され、ベクトルデータが生成される。この図形
記述からベクトルデータが生成される状態を以下の図１
３に示す。

【００５２】図１３は量子化部におけるベクトルデータ
の生成状態を示す図である。量子化部４３では、最適化
された図形記述をベクトル化するときには、それぞれ要
素図形記述の後ろに交点情報が付加されているので、そ
れを参照しながらベクトルデータを生成する。要素図形
の直線分のベクトルデータを作るときには、そのベクト
ルの向きについては、要素図形記述の始点および終点の
情報で示されるが、長さは、その要素図形上の交点まで
とする。たとえば、図形６０の第２辺の要素図形６０ｂ
のベクトルデータを作るときには、基本的なベクトルの
向きは始点および終点の記述で示されるが、座標（２２
５，３００）の位置で図形８０の第１辺と交わるという
ことが記述されているので、その交わる位置までしかベ
クトルは生成せず、この結果、ベクトルデータ６０ｂ−
１が生成される。一方、図形７０の第１辺のような要素
図形の曲線分については、微小直線分の系列で近似す
る。次に、交点情報を用いて実際に描画される図形の境
界を決定する。たとえば、図形６０の第３辺は三つの部
分に分割され、分割位置においては図形７０および図形
８０と境界を共有する。

【００５３】こうして得られたベクトルデータは出力処
理部４５に渡され、出力処理が行われるが、この出力処
理について以下に説明する。図１４は出力処理部におけ
るベクトルデータのラスタ化を示す図である。出力処理
部４５がベクトルデータから印字可能な出力データを作
成する場合、図１４に示すようにページの上から順に走
査していって、走査線と交わるベクトルを求め、走査線
とベクトルの交点が図形の境界であり色が変化する点で
あると判断して、図形の色属性に従って次の交点まで塗
りつぶしを行う。この動作をページを構成する全ての走
査線について行うことで１ページ分の印字可能な出力デ
ータが生成される。ただし、出力処理部においては重な
り処理を行わないため、１ページ分の出力データを同時
にメモリ上に保持してそのメモリ上で重なり処理を行う
必要がない。また、入力の順序を考慮する必要がないた
め、ベクトルデータを分割して並列処理することも可能
である。

【００５４】次に、第２の発明の実施の形態を、ネット
ワークに接続された印刷システムに適用した場合を例に
して説明する。図１５は本発明による画像形成装置を適
用したネットワーク印刷システムの構成例を示す図であ
る。ネットワーク印刷システムは、複数のクライアント
計算機１０１，１０２，１０３，・・・と、ネットワー
ク１１０と、プリントサーバ１２０と、プリントエンジ
ン１３０とから構成され、本発明による画像形成装置は
プリントサーバ１２０の一部として適用されている。プ
リントサーバ１２０は、ネットワーク１１０に接続され
た命令解析部１２１と、量子化部１２２と、図形記述更
新部１２３と、ページバッファ１２４と、出力処理部１
２５とが共有バス１２６によって相互に接続されてい
る。プリントサーバ１２０は、また、ページバッファ１
２４と出力処理部１２５とに接続された退避部１２７
と、出力処理部１２５に接続されたプリンタインタフェ
ース１２８とを備えており、このプリンタインタフェー
ス１２８の出力はプリントエンジン１３０に接続されて
いる。

【００５５】クライアント計算機１０１，１０２，１０
３，・・・で作成された印刷ジョブはネットワーク１１
０を介してプリントサーバ１２０の命令解析部１２１に
送られる。命令解析部１２１では、受け取った印刷ジョ
ブの内容をページ記述言語の命令列として解釈実行し、
個々の描画図形を表す図形記述を生成する。生成された
図形記述は量子化部１２２に送られベクトル化される。
量子化部１２２の出力であるベクトルデータは、ページ
バッファ１２４に送られ保存される。このとき、既にペ
ージバッファ１２４に保存されている図形と新たに生成
された図形との間に重なりがある場合には、重なりの優
先度に基づいて図形記述更新部１２３によってベクトル
データが更新される。ページの終端を示す命令が検出さ
れると、ページバッファ１２４に保存されているベクト
ルデータは、出力処理部１２５に送られ印字可能な形式
の出力データが生成される。出力処理部１２５の出力で
ある出力データは、プリンタインタフェース１２８を介
してプリントエンジン１３０に送られ印刷される。

【００５６】命令解析部１２１は、入力として与えられ
たページ記述言語の命令列を順に解釈実行し、図形記述
を生成する。命令解析部１２１によって生成された図形
記述は量子化部１２２によってベクトル化される。これ
は曲線を微小線分で近似する処理から成り、その詳細は
前述の通りである。

【００５７】量子化部１２２によって生成されたベクト
ルデータは、順にページバッファ１２４に保存される。
たとえば、第１のベクトルデータを新たにページバッフ
ァ１２４に登録する際に、その第１のベクトルデータが
表現する図形が既に登録された第２のベクトルデータの
表現する図形と重なる場合には、図形記述更新部１２３
によってそれらのベクトルデータの間で重なり優先度の
低い記述に重なり情報が付加される。この処理の流れは
第１の発明の実施の形態と同様であるが、ベクトル同士
の交点の座標を求めることは直線の交点を求める問題で
あり容易に解くことができる。

【００５８】上述の動作をページの終端を表す命令を検
出するまで繰り返して、１ページ分のベクトルデータを
ページバッファ１２４に生成すると、次にページバッフ
ァ１２４に蓄積されたベクトルデータに含まれる重なり
情報の最適化を行う。これは、交点情報に対する二つの
操作から成る処理である。まず、それぞれの要素ベクト
ル記述に付加された交点記述をその交点の座標値を用い
て整列する。整列の方法は第１の発明の実施の形態と同
様である。

【００５９】次に他の図形との重なりの下になる交点情
報を調べ削除する。この処理の詳細は第１の発明の実施
の形態と同様である。上述の処理によって得られたベク
トルデータは、出力処理部１２５によって出力形式に変
換される。この出力処理部１２５は、印刷可能画像デー
タを生成する処理と、それまでに処理したベクトルデー
タを退避部１２７に退避して保存しておく処理のいずれ
かを行う。この退避部を実現するための装置は、メモリ
で構成される主記憶でもディスクなどの二次記憶でも構
わない。

【００６０】退避部１２７によって退避されたベクトル
データは、ページバッファ１２４に読み込まれ、以降に
生成されるベクトルデータとの重なり処理を行うことに
より、再利用が可能である。

【００６１】以上の手続きを具体的な図形記述に適用し
た例を示す。たとえば、図９の（Ａ）および（Ｂ）に示
すそれぞれの図形を表すページ記述言語入力６１および
７１が与えられると、命令解析部１２１によってそれぞ
れ図形記述６２および７２が生成される。このとき、そ
れぞれの図形記述６２，７２には図形を一意に特定する
ための識別子と重なりの優先順位を表す重なり優先度が
付加される。こうして生成された図形記述６２，７２は
順に量子化部１２２へと送られ、そこでベクトルデータ
が生成される。

【００６２】図１６はベクトル化イメージの描画図形お
よび対応するベクトルデータを示す図である。図１６の
（Ａ）は描画される三角形の図形６０と、この図形６０
を表すページ記述言語入力６１から生成されたベクトル
データ６３とを示しており、図１６の（Ｂ）は描画され
る扇形の図形７０と、この図形７０を表すページ記述言
語入力７１から生成されたベクトルデータ７３とを示し
ている。

【００６３】図示のように量子化部１２２では、要素図
形の直線分については、そのままベクトル化され、図形
７０の第１辺のような曲線分は、微小直線分の系列で近
似される。そして、量子化部１２２の出力であるベクト
ルデータは次にページバッファ１２４に送られる。

【００６４】図１７は重なり検出時の交点情報を付加す
る処理の説明図である。図１７の（Ａ）は図形６０，７
０の重なり状態を示し、図１７の（Ｂ）は重なり情報が
付加された図形６０のベクトルデータ６３ａを示してい
る。ページバッファ１２４では、新たなベクトルデータ
を登録する際にはそのベクトルデータが表す図形の描画
領域と既に登録されたベクトルデータが表す図形の描画
領域とが重なるかどうかを調べ、重なりがある場合には
重なりの下になるベクトルデータに重なり情報を付加す
る。ベクトルデータ６３が登録され、次にベクトルデー
タ７３が登録される際には、重なり判定が行われ、重な
りが検出される。するとベクトルデータ６３に含まれる
要素ベクトルのそれぞれに対してベクトルデータ７３に
含まれる要素ベクトルが表す要素図形との重なりを調
べ、重なり優先度の低いベクトルデータの要素ベクトル
に交点情報を付加する。この交点情報には、この要素ベ
クトルと重なる要素ベクトルを特定するための図形の識
別子と要素ベクトルのベクトルデータ中での出現順序お
よび交点の座標が含まれている。このようにして、ベク
トルデータ６３に交点情報が付加されると、図示のベク
トルデータ６３ａとなる。

【００６５】次に、同様にして、３つ目の図形が追加さ
れた場合について説明する。この新たな図形は図１２に
おいて示した図形記述８２によって表されるものとす
る。図１８は新たな図形が追加されたときの重なり検出
状態を示す図、図１９はベクトルデータに交点情報を付
加して最適化する処理の説明図である。図１８によれ
ば、図形６０の上に図形７０が重なっている状態で、さ
らに新たに平行四辺形の図形８０が図形６０，７０の一
部に重なるように追加して描画される状態を示してい
る。そして、重なり検出の結果、互いに重なり合う要素
ベクトルの位置には交点情報を表す小さな丸が付加され
ている。

【００６６】この図１８の重なり状態の各図形に対応す
る図形記述を図１９に示してある。ベクトルデータ６３
ａはベクトルデータ６３ｂに、ベクトルデータ７３はベ
クトルデータ７３ａになり、さらに、図形８０のベクト
ルデータ８３が示されている。ここで、ページの終端を
表す命令が検出されると、重なり記述の最適化が行われ
る。図形６０の第２辺に現れる交点のうち、図形７０の
第１３辺との交点は、図形７０よりも重なり優先度の高
い図形８０の第１辺との交点と図形８０の第３辺との交
点とに挟まれており、最適化部によって取り除かれる。
この結果、図形６０のベクトル記述はベクトルデータ６
３ｃのように最適化される。

【００６７】こうして最適化されたベクトルデータは出
力処理部１２５に渡され、出力処理が行われる。出力処
理部１２５が印字可能な出力データを作成する場合、第
１の発明の実施の形態と同様にしてラスタ化されて印字
可能な出力データが生成される。

【００６８】また、出力処理部１２５はベクトルデータ
を退避部１２７に退避し、これをページバッファ１２４
が初期値として読み込んで利用することで、オーバレイ
処理などでのページデータの再利用を少ないメモリで実
現することができる。

【００６９】以上、第２の発明の実施の形態の詳細を示
したが、図１５に例示した構成において、図形記述更新
部１２３による図形記述レベルでの重なり検出および最
適化を先に行い、量子化部１２２におけるベクトル化を
出力処理部１２５によるラスタ化の直前に行うようにす
ることにより、オーバレイ処理が可能な第１の発明の実
施の形態とすることができる。

【００７０】

【発明の効果】以上説明したように第１の発明では、描
画図形記述生成手段で生成された描画図形記述を保持す
る図形記述保持手段と、図形記述保持手段が保持する描
画図形記述の重なり関係に基づいて描画図形記述に重な
り情報を付加するように描画図形記述を更新する記述更
新手段とを備えるように構成した。これにより、画像デ
ータのレベルでなく、より抽象度の高いレベルの描画図
形記述で、すなわち、データ量の小さなレベルで重なり
処理をするので、メモリ使用量を抑えることができる。

【００７１】また、第２の発明では、ベクトル記述生成
手段で生成されたベクトル記述を保持するベクトル記述
保持手段と、このベクトル記述保持手段が保持するベク
トル記述の重なり関係に基づいてベクトル記述に重なり
情報を付加するようにベクトル記述を更新する記述更新
手段とを備えるように構成した。これにより、画像デー
タのレベルでなく、より抽象度の高いレベルのベクトル
記述で、すなわち、データ量の小さなレベルで重なり処
理をするので、メモリ使用量を抑えることができる。

【００７２】さらに、オーバレイ処理などの際にも、重
なり処理を画像データよりもより抽象度の高いレベルで
行うので、プリンタシステムのメモリ使用量とデータ転
送の負荷を抑えることが可能になる。

【図面の簡単な説明】

【図１】第１の発明の原理構成を示す図である。

【図２】第２の発明の原理構成を示す図である。

【図３】本発明による画像形成装置を適用したネットワ
ーク印刷システムの構成例を示す図である。

【図４】重なり判定手続きの処理の流れを示すフローチ
ャートである。

【図５】重なり情報の付加処理の流れを示すフローチャ
ートである。

【図６】整列処理の流れの例を示すフローチャートであ
る。

【図７】最適化処理の流れを示すフローチャートであ
る。

【図８】別の最適化処理の流れを示すフローチャートで
ある。

【図９】描画図形および対応するページ記述言語入力お
よび図形記述を示す図である。

【図１０】重なり検出時の交点情報を付加する処理の説
明図である。

【図１１】新たな図形が追加されたときの重なり検出状
態を示す図である。

【図１２】図形記述に交点情報を付加して最適化する処
理の説明図である。

【図１３】量子化部におけるベクトルデータの生成状態
を示す図である。

【図１４】出力処理部におけるベクトルデータのラスタ
化を示す図である。

【図１５】本発明による画像形成装置を適用したネット
ワーク印刷システムの構成例を示す図である。

【図１６】ベクトル化イメージの描画図形および対応す
るベクトルデータを示す図である。

【図１７】重なり検出時の交点情報を付加する処理の説
明図である。

【図１８】新たな図形が追加されたときの重なり検出状
態を示す図である。

【図１９】ベクトルデータに交点情報を付加して最適化
する処理の説明図である。

【符号の説明】

１描画図形記述生成手段２図形記述保持手段３記述更新手段４ベクトル記述生成手段５出力処理手段６二次記憶手段１１描画図形記述生成手段１２ベクトル記述生成手段１３ベクトル記述保持手段１４記述更新手段１５出力処理手段１６二次記憶手段

Claims

【特許請求の範囲】

【請求項１】ページ記述言語で記述された画像描画命
令を実行して出力画像を得るための画像形成装置におい
て、入力された前記画像描画命令を解釈して描画図形の外形
を表す有向直線分および有向曲線分の列、描画図形識別
子、および重なり優先度から成る描画図形記述を生成す
る描画図形記述生成手段と、前記描画図形記述生成手段で生成された描画図形記述を
保持する図形記述保持手段と、前記図形記述保持手段が保持する描画図形記述の重なり
関係に基づいて描画図形記述に重なり情報を付加するよ
うに前記描画図形記述を更新する記述更新手段と、前記図形記述保持手段に保持された描画図形記述からベ
クトル記述を生成するベクトル記述生成手段と、前記ベクトル記述生成手段によって生成されたベクトル
記述を用いて印字可能な形式の出力データを生成する出
力処理手段と、を備えていることを特徴とする画像形成装置。
【請求項２】前記記述更新手段は、描画図形を構成す
る有向直線分または有向曲線分の記述に、前記有向直線
分または有向曲線分と交差する他の描画図形記述を構成
する有向直線分または有向曲線分を特定する識別子と交
点の座標とを重なり情報として付加するように構成した
ことを特徴とする請求項１記載の画像形成装置。
【請求項３】前記記述更新手段は、描画図形記述を構
成する有向直線分および有向曲線分の記述に現れる交点
を前記有向直線分および有向曲線分の向きに従って整列
し、整列された交点のうち重なり優先度の高い図形との
交点の内部にあってその図形よりも重なり優先度の低い
図形との交点を削除することにより前記重なり情報の最
適化を行うように構成したことを特徴とする請求項２記
載の画像形成装置。
【請求項４】前記図形記述保持手段に保持された描画
図形記述をテンプレートとして退避し、別の画像描画命
令の入力時には、退避された前記描画図形記述が前記図
形記述保持手段に読み込まれて前記記述更新手段による
記述更新の動作の初期値となる、二次記憶手段をさらに
備えていることを特徴とする請求項１記載の画像形成装
置。
【請求項５】ページ記述言語で記述された画像描画命
令を実行して出力画像を得るための画像形成装置におい
て、入力された前記画像描画命令を解釈して描画図形の外形
を表す有向直線分および有向曲線分の列、描画図形識別
子、および重なり優先度から成る描画図形記述を生成す
る描画図形記述生成手段と、前記描画図形記述生成手段で生成された描画図形記述か
らベクトル記述を生成するベクトル記述生成手段と、前記ベクトル記述生成手段で生成されたベクトル記述を
保持するベクトル記述保持手段と、前記ベクトル記述保持手段が保持するベクトル記述の重
なり関係に基づいてベクトル記述に重なり情報を付加す
るように前記ベクトル記述を更新する記述更新手段と、前記ベクトル記述保持手段によって保持されたベクトル
記述を用いて印字可能な形式の出力データを生成する出
力処理手段と、を備えていることを特徴とする画像形成装置。
【請求項６】前記記述更新手段は、描画図形ベクトル
を構成する要素ベクトルの記述に、前記要素ベクトルと
交差する他の要素ベクトルを特定する識別子と交点の座
標とを重なり情報として付加するように構成したことを
特徴とする請求項５記載の画像形成装置。
【請求項７】前記記述更新手段は、描画図形ベクトル
を構成する要素ベクトルの記述に現れる交点を前記要素
ベクトルの向きに従って整列し、整列された交点のうち
重なり優先度の高い図形との交点の内部にあってその図
形よりも重なり優先度の低い図形との交点を削除するこ
とにより前記重なり情報の最適化を行うように構成した
ことを特徴とする請求項６に記載の画像形成装置。
【請求項８】前記ベクトル記述保持手段に保持された
ベクトル記述をテンプレートとして退避し、別の画像描
画命令によるベクトル記述が与えられるときには、退避
された前記ベクトル記述が前記ベクトル記述保持手段に
読み込まれて与えられたベクトル記述に対して前記記述
更新手段による記述更新が行われる、二次記憶手段をさ
らに備えていることを特徴とする請求項５記載の画像形
成装置。
【請求項９】ページ記述言語で記述された画像描画命
令を実行して出力画像を得るための画像形成方法におい
て、入力された前記画像描画命令を解釈して描画図形の外形
を表す有向直線分および有向曲線分の列、描画図形識別
子、および重なり優先度から成る描画図形記述を生成
し、生成された描画図形記述のレベルで描画図形記述の重な
り関係に基づいた重ね合わせの処理を行い、重ね合わせ処理された描画図形記述からベクトル記述を
生成し、生成されたベクトル記述から印字可能な形式の出力デー
タを生成する、ことからなる画像形成方法。
【請求項１０】前記重ね合わせの処理を行うステップ
は、描画図形を構成する有向直線分または有向曲線分の
記述に、前記有向直線分または有向曲線分と交差する他
の描画図形記述を構成する有向直線分または有向曲線分
を特定する識別子と交点の座標とを付加するステップを
有することを特徴とする請求項９記載の画像形成方法。
【請求項１１】前記重ね合わせの処理を行うステップ
は、描画図形記述を構成する有向直線分および有向曲線
分の記述に現れる交点を前記有向直線分および有向曲線
分の向きに従って整列し、整列された交点のうち重なり
優先度の高い図形との交点の内部にあってその図形より
も重なり優先度の低い図形との交点を削除するステップ
をさらに有することを特徴とする請求項１０記載の画像
形成方法。
【請求項１２】ページ記述言語で記述された画像描画
命令を実行して出力画像を得るための画像形成方法にお
いて、入力された前記画像描画命令を解釈して描画図形の外形
を表す有向直線分および有向曲線分の列、描画図形識別
子、および重なり優先度から成る描画図形記述を生成
し、生成された描画図形記述からベクトル記述を生成し、生成されたベクトル記述のレベルでベクトル記述の重な
り関係に基づいた重ね合わせの処理を行い、重ね合わせ処理されたベクトル記述から印字可能な形式
の出力データを生成する、ことからなる画像形成方法。
【請求項１３】前記重ね合わせの処理を行うステップ
は、描画図形ベクトルを構成する要素ベクトルの記述
に、前記要素ベクトルと交差する他の要素ベクトルを特
定する識別子と交点の座標とを付加するステップを有す
ることを特徴とする請求項１２記載の画像形成方法。
【請求項１４】前記重ね合わせの処理を行うステップ
は、描画図形ベクトルを構成する要素ベクトルの記述に
現れる交点を前記要素ベクトルの向きに従って整列し、
整列された交点のうち重なり優先度の高い図形との交点
の内部にあってその図形よりも重なり優先度の低い図形
との交点を削除するステップをさらに有することを特徴
とする請求項１３記載の画像形成方法。