(57)【特許請求の範囲】
【請求項１】
オーバーラップしたオブジェクトに対してトラッピングを行うために少なくとも１個のオブジェクトを有する頁情報を表示するコンピュータによって実施される方法において、
（ａ）ＰＤＬフォーマットで表現されている１頁を少なくとも一つの画像情報タイルへセグメント化し、
（ｂ）各タイルを複数個のセルを有しているグリッドアレイとして表わし、該セルは輪郭セグメントからなるエッジリストを有しており、
（ｃ）前記グリッドアレイ上に表われる各オブジェクトに対する前記輪郭セグメントでもって、前記エッジリストから前記複数個のセルの内で前記輪郭セグメントが通過する少なくとも１個のセルを決定し、
（ｄ）前記複数個のセルの内で２個以上の輪郭セグメントが通過するセルに対してのみ前記グリッドアレイ内の複数個の輪郭セグメントの間の少なくとも１個の交差部を決定し、
（ｅ）前記各交差部において前記輪郭セグメントを分割し、
（ｆ）前記分割された輪郭セグメントの内で他のオブジェクトによって隠される輪郭セグメントを除去し、
（ｇ）他のオブジェクトによって隠されることのない残存する輪郭セグメントに対してトラッピングを行う、
上記各ステップを有することを特徴とする方法。
【請求項２】
請求項１において、更に、
（ａ）どのセルが交差する輪郭セグメントの表示を有しているかを決定し、
（ｂ）この様な表示から、前記交差する輪郭セグメントのどれが少なくとも一つの他のオブジェクトによって隠されるかを決定する、
上記各ステップを有することを特徴とするコンピュータ方法。
【請求項３】
請求項２において、更に、
（ａ）この様な表示から各輪郭セグメントの両側に対するカラーを決定する、上記ステップを有することを特徴とするコンピュータ方法。
【請求項４】
オーバーラップしたオブジェクトに対してトラッピングを実行するために少なくとも１個のオブジェクトを有する頁情報を表わすコンピュータシステムにおいて、
（ａ）ＰＤＬフォーマットで表現されている１頁を少なくとも１個の画像情報タイルへセグメント化する手段、
（ｂ）各タイルを複数個のセルを有しているグリッドアレイとして表わす手段であって該セルは輪郭セグメントからなるエッジリストを有している手段、
（ｃ）前記グリッドアレイ上に表われる各オブジェクトに対する前記輪郭セグメントでもって、前記エッジリストから前記複数個のセルの内で前記輪郭セグメントが通過する少なくとも１個のセルを決定する手段、
（ｄ）前記複数個のセルの内で２個以上の輪郭セグメントが通過するセルに対してのみ前記グリッドアレイ内の複数個の輪郭セグメント間の少なくとも１個の交差部を決定する手段、
（ｅ）前記各交差部において前記輪郭セグメントを分割する手段、
（ｆ）前記分割された輪郭セグメントの内で他のオブジェクトによって隠される輪郭セグメントを除去する手段、
（ｇ）他のオブジェクトによって隠されることのない残存する輪郭セグメントに対してトラッピングを行う手段、
を有することを特徴とするコンピュータシステム。
【請求項５】
請求項４において、更に、
（ａ）どのセルが交差する輪郭セグメントの表示を有しているかを決定する手段、
（ｂ）この様な表示から、前記交差する輪郭セグメントの何れが少なくとも一つの他のオブジェクトによって隠されるかを決定する手段、
を有することを特徴とするコンピュータシステム。
【請求項６】
請求項５において、更に、
（ａ）この様な表示から各輪郭セグメントの両側に対するカラーを決定する手段、
を有することを特徴とするコンピュータシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一組のオーバーラップするオブジェクトの平坦化技術に関するものであって、更に詳細には、電子印刷システムにおけるカラートラッピング技術に関するものである。
【０００２】
【従来の技術】
長年の間、用紙上へのカラー印刷に対する好適なプロセスは、複数個の露光即ちセパレーションで頁を処理するものであった。各セパレーション（ｓｅｐａｒａｔｉｏｎ）は、用紙の選択された区域を異なるカラーのインクへ露光させる。通常のプロセスインクカラーはシアン、マゼンタ、イエロ及び「キー」（ＣＭＹＫ）であって、キーは通常黒である。付加的なセパレーションにおけるスポットカラーとして、付加的なカラーインクがしばしば使用される。
【０００３】
例えば印刷業界において必要とされるような高品質の印刷は、セパレーションを制御する場合に多くの困難な問題を提起する。例えば、カラー印刷は、用紙がプリンタのプレートを介して多数回パスを行うので、用紙が適切に整合されない場合にはカラー印刷において妥協が行われる。その結果、幾つかのインクは完全に互いに整合することはなく、且つ異なるカラーの領域間に小さなギャップが発生する場合があり、それは、しばしば、オフカラー（ｏｆｆ−ｃｏｌｏｒ）即ち色ずれのラインとして極めて目立つものである。この問題は、典型的に、不整合と呼ばれる。
【０００４】
この不整合問題に対する一つの一般的な解決方法は、「トラッピング」と呼ばれる技術を使用することである。カラーセパレーション即ち色分解が発生される場合に、より明るいカラーの領域を通常の境界を超えて拡大即ち「スプレッド」させることが可能であり、一方より暗いカラーの領域をこの様な境界内において収縮即ち「チョーク」させて、２番目及びそれ以後のインクパスに関するカラーのオーバーラップを形成させることが可能である。この様なオーバーラップ即ち重ね合わせは、不整合の効果を緩和させる。トラッピング技術は、従来、手作業によって行われていた。厄介なものであるが、過去においては、手作業のトラッピング技術が、各印刷される頁に対する個々のトラップを形成するために必要とされる時間及び労力が経済的に正当化される例えば雑誌出版などの適用場面において使用されており、又は、印刷の品質が重要であるパッケージングにおいて使用されている。
【０００５】
最近においては、印刷業界において新たな種類の低コストの適用例が出現しており、即ち「デスクトップ」パブリッシングが出現している。デスクトップパブリッシングシステムユーザは、典型的に、例えば「ポストスクリプト（Ｐｏｓｔｓｃｒｉｐｔ）」などの頁記述言語（ＰＤＬ）でコンピュータファイルとして出力頁を特定するためにスタンダードのパソコンを使用する。尚、ポストスクリプトはカリフォルニア州マウンテンビュのアドビシステムズインコーポレイテッドの商標である。次いで、そのＰＤＬファイルを、典型的に、ＰＤＬ互換性のある自動頁セッタへ送られ、該セッタがそのファイルを解釈し且つ後にオフセット印刷プレートのホトリソグラフィ製造を行うためにフイルム上に幾つかのカラーセパレーション即ち色分解を施す。
【０００６】
最近において、トラッピングを電子的に行うコンピュータシステムが広く使用されるようになっている。電子トラッピングへの一つのアプローチは、元のプログラムもグラフィックスに対するトラップを形成させることである。一例として、例えばＡｌｄｕｓ  Ｆｒｅｅｈａｎｄ（商標）などの描画プログラムにおいては、ユーザは、トラッピングを受付けるためにオブジェクトの周りにアウトラインを付加することが可能である。元のプログラムレベルにおけるトラッピングアプローチは有益的なものである。なぜならば、付加的なトラッピングコストを除去することが可能であり、即ち後処理プログラム又は従来のトラッピング技術を使用することが必要ではないからである。しかしながら、元のプログラムにおけるトラッピング能力は、典型的に、非常に制限されている。一つの欠点は、バックグラウンド及び／又はフォアグラウンドが多数の異なるカラーのオブジェクトによって形成されている状態において明らかである。この状態は、例えば、個々のテキストキャラクタが一つを超えるオブジェクトとオーバーラップする場合に発生する。トラッピング能力を有する典型的な元のプログラムは、テキスト又はボックスなどのオブジェクトを比較的粗雑な態様で取扱う傾向があり、従って、トラップはテキストボックス全体に適用することが可能であるに過ぎないか、又は良い場合でも、キャラクタ全体に対して適用することが可能であるに過ぎない。従って、これらの場合におけるトラッピングの結果は所望するものより程度が劣っている。更に、トラップパラメータ（例えば、オーバーラップ幅）は各印刷プロセスの特性に対して特定的なものであるので、これらの値は、典型的に、文書が作成される時に使用可能なものではなく、且つコンテント即ち内容物の作成者が印刷特性の十分なる知識を有することを必要とすることは、これらのプログラムのユーザに付加的な負担を与えることとなる。
【０００７】
「ラスタートラッピング」として知られる自動化したアプローチは、（１）１頁を定義するＰＤＬファイルで開始し、（２）該ＰＤＬファイル内のベクトルグラフィックス及び／又はテキストをラスター画像プロセサ（ＲＩＰ）によって所望の出力分解能でラスター（ビットマップ）画像へ変換し、（３）該画像を構成するピクセルデータを使用してラスター画像をトラップするものである。この第三ステップは、通常、各セパレーションに対してフレームバッファ内に別個の面を作成することを必要とする。次いで、該フレームバッファの面をピクセル毎にトラップし、その結果を使用して各面のそれぞれのカラーの印刷を制御する。理解されるように、このアプローチは非常にメモリ集約的であり、且つ入力／出力が縛られたものである（無制限のメモリを有するコンピュータの場合であっても問題である）。
【０００８】
ラスタートラッピングの利点は、（１）ＲＩＰインタプリタが、既に、フレームバッファにおけるエッジのカラー及び相互作用を処理しており、且つ（２）カラーの遷移を見つけ出すために使用される動作は非常に簡単であり且つ単一のフレームバッファピクセルを処理するための動作の複雑性は一定である（即ち、それは局所化されている動作である）ということである。ラスターをベースとしたトラッピングの欠点は、（１）全フレームバッファがレンダリングされ且つカラー変化に対して検査されねばならず、且つ（２）フレームバッファ寸法は頁寸法及び分解能の平方と共に増加し且つインクの数と共に線形的に増加する。これらのファクタは高いデータ処理能力条件を課すものである。
【０００９】
より最近の自動化したアプローチは、本願出願人に譲渡されており「頁記述言語フォーマットで特定された印刷頁へのトラップの適用（Ａｐｐｌｙｉｎｇ  Ｔｒａｐｓ  ｔｏ  ａ  Ｐｒｉｎｔｅｄ  Ｐａｇｅ  Ｓｐｅｃｉｆｉｅｄ  ｉｎ  ａ  Ｐａｇｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ  Ｆｏｒｍａｔ」）という名称の米国特許第５，２９５，２３６号に記載されている。この’２３６特許は、デスクトップパブリッシング、レイアウト、グラフィックス又は同様のアプリケーションプログラムにおいてプリントしたカラー頁を電子的にトラッピングする方法及び装置を開示している。この方法は、プリントした頁を構成するＰＤＬ命令をプリントした頁内のカラー領域間のエッジの検知及び解析に適したベクトルをベースとしたフォーマットへ翻訳し、一組のトラッピング規則に従って、該カラーエッジにおいて一組のトラップを作成し、且つＰＤＬフォーマットで表現された該トラップを包含するトラップ出力ファイルを生成する。該ＰＤＬファイルが印刷のために解釈されると、該トラップは元のデータと同一の態様で処理される。
【００１０】
ベクトルをベースとしたトラッピングの利点は、（１）事実上、ＰＤＬフォーマットで表現されている任意の印刷した頁をそのグラフィックスを最初に作成したアプリケーション、即ち元のプログラムに拘らずに、トラップすることが可能であり、（２）一般的に、エッジ数はフレームバッファ内のピクセル数と比較して比較的小さく、（３）エッジ数は分解能に関してほぼ線形的であり且つデータがセパレーションインクの数と比較的独立的であるということである。ベクトルをベースとしたトラッピングの欠点は、（１）エッジ及びオブジェクトの相互作用はトラップエンジンによって決定されねばならず、且つ（２）ベクトルを処理するために使用される操作はラスター操作と比較して比較的複雑であり、且つ単一のエッジを処理する場合に関与する複雑性はエッジ数と共に増加するということである。
【００１１】
上述したことから、これら二つの自動化したアプローチの利点及び欠点はほぼ相互に排他的なものであることが明らかである。勿論、疎らなエッジ分布を有する簡単なアートワークからエッジ密度が高い複雑なアートワークへ移行すると、性能利点はベクトルをベースとしたトラッピングからラスターをベースとしたトラッピングへ推移する。
【００１２】
【発明が解決しようとする課題】
実現化が比較的簡単であり、任意の頁を処理することが可能であり、且つ従来方法と比較して大型のメモリ又はプロセサ資源を必要とすることのない自動的に頁をトラッピングする方法及びシステムを提供することが所望されている。本発明は、以上の点に鑑みなされたものであって、この様な方法及びシステムを提供することを目的とする。本発明の最も一般的な実現例は、更に、一組のオブジェクトを平坦化させる（即ち、一組のオーバーラップするオブジェクトをオーバーラップしない一組のオブジェクトへ還元させる）方法を提供している。
【００１３】
【課題を解決するための手段】
本発明は、特に、トラッピングを実行するため、且つ、より一般的な場合においては、一組のオブジェクトを平坦化させるため（即ち、一組のオーバーラップするオブジェクトを一組のオーバーラップしないオブジェクトへ還元すること）に頁情報のベクトルマップ表示を使用する。該ベクトルマップ表示は、ベクトル表示の疎らさとラスター表示の一定単位の複雑性とを結合させることによりトラッピングをより効率的なものとさせるためにラスターをベースとした表示とベクトルをベースとした表示の両方のポジティブな属性を結合している。
【００１４】
本発明の好適実施例においては、１頁がタイトルで定義され、且つ各タイトルはベクトルマップ（ビットマップに対する類推として）と呼称されるエッジポインタからなる２Ｄアレイへマップされる。該ベクトルマップ内の各セルは、それを通過する画像のエッジの全てのリストを有している。一対のエッジは、それらが同一のベクトルマップセルリスト内に存在する場合にのみ相互作用することが可能である。従って、エッジ交差及びカラー見つけ出しテストはラスターをベースとしたトラッピングの場合の如く局所化されているが、一方ベクトルをベースとしたトラッピングのデータの疎らさは維持されている。適切に選択されたベクトルマップ寸法の場合には、単一のエッジは、通常、多くのセルと交差するものではない。一方、カッドツリー（ｑｕａｄ−ｔｒｅｅ）表示を使用することが可能であり、それは適応的にセルを細分化する。エッジ交差及びカラー見つけ出しテストを適用することは、効果的に、頁上のオブジェクトを平坦化させる。カラートラッピングの場合には、トラッピング関数を、ベクトルマップから決定されるようなエッジへ適用する。
【００１５】
本発明のベクトルマップ表示側面の幾つかの利点は以下のようなものである。
（１）複雑なＰＤＬ頁及び多数の小さなエッジセグメントを有するＰＤＬ頁（例えば、多くのフォント、ビネット、パターンなど）においてエッジ交差を決定する場合に関与する複雑性の減少。
【００１６】
（２）エッジ間の相対的な空間的関係の捕獲及び維持；この情報はトラッピングにおいて関与する種々のステップを介して伝搬される（オブジェクト交差、トラップカラー選択を介しての隠れたベクトルの除去、トラップ配置及びトラップ整形から）。ベクトルマップ表示は疎らなフォーマットにおけるエッジ間の空間的関係を捕獲し且つ格納するために簡単且つ効果的な態様である。純粋のベクトルをベースとしたアプローチにおける代替物は、通常、エッジ間の空間的関係を決定する。
【００１７】
（３）他の基本的なデータ構造がほとんど変化なしで全トラッピングプロセスを介して伝搬され且つデータの疎らさが維持されるので、トラッピングアルゴリズムの複雑性が減少される。典型的に、純粋なベクトルをベースとしたアプローチは、データ（エッジ点）が種類分けしたリスト内に維持されることを必要とする。
【００１８】
（４）入力データに対する適応が容易であり、タイトル当たり小さな数のエッジがより粗いグリッドを発生し、且つタイトル当たり多数のエッジがより微細なグリッドを発生する。
【００１９】
（５）グリッドにおけるセルがクワッドツリーデータ構造に細分化され、その場合に該クワッドツリーのリーフ（ｌｅａｆ）ノードがエッジリストへ指向する、階層的ベクトルマップ表示へ拡張する能力。この様な表示においては、高いエッジ密度を有する区域がより少ないエッジを有するものよりもより微細に細分化されるように、セルが区画化される。
【００２０】
（６）ラスタライズしたビットマップで使用すべく修正可能であり、ベクトルマップがラスターマップ上に重ね合わせられると、該ラスターマップはエッジ相互作用を解決するために使用することが可能である。この様な方法においては、ラスターマップ内に対応するエッジが存在しておらず且つエッジカラーがラスターマップから決定される場合に、エッジがベクトルマップから削除される。エッジをベクトルマップ内にトラップさせることが可能であり且つ該トラップはラスタライズした頁の出力前にマップ内に直接ペイントさせることが可能である。
【００２１】
【発明の実施の形態】
概観
本発明の好適実施例においては、１頁がタイトルで定義され、且つ各タイトルはベクトルマップ（ビットマップに対する類推）として呼称されるエッジポインタからなる２Ｄアレイへマップされる。ベクトルマップ内の各セルは、それを通過する画像の全てのエッジからなるリストを有している。一対のエッジは、それらが同一のベクトルマップセルリスト内に存在する場合にのみ、相互作用することが可能である。従って、エッジ相互作用などの平坦化機能、エッジカラー見つけ出し、隠されたエッジ除去、トラップ整形、及びエッジフィルタテストはラスターをベースとしたトラッピングの場合におけるように全てのステップ期間中局所化されており、一方、ベクトルをベースとしたトラッピングのデータの疎らさは維持される。適切に選択したベクトルマップ寸法の場合には、単一のエッジは、通常、多数のセルと交差することはない。カラートラッピングの場合には、トラッピング関数がベクトルマップから決定された可視的なエッジに対して適用され、且つトラップポリゴンが該ベクトルマップ上に発生される。
【００２２】
より詳細に説明すると、１頁を平坦化する場合にベクトルマップ表示概念を適用するためには、その頁を等しい区域の正方形のタイル（例えば、約０．５インチ以下）に分割する。各タイルは、そのタイルと交差する全てのポリゴン即ち多角形がエンタされるタイルに対するベクトルマップを構成することによって独立的に平坦化される。ポリゴンの輪郭は例えば、迅速な線描画アルゴリズム（例えば、Ｂｒｅｓｅｎｈａｍのアルゴリズム）又はルックアップテーブル（ベクトルマップ内のセル数が大きくない場合には実際的なものである）でベクトルマップ内に描画させることが可能である。ポリゴンとタイルとの交差は、簡単な取囲みボックステストで決定することが可能である。
【００２３】
好適なトラッピング実施例においては、１個のタイルに対するベクトルマップの初期的なセル寸法は推定された平均ポリゴンエッジに比例するものとされ且つ最大トラップポリゴン幅（トラッピングアプリケーションへの入力パラメータ）よりも一層大きなものに構成される。平均ポリゴンエッジ長さＥ＿は以下の如くに推定することが可能である。
【００２４】
Ｅ＿＝（ポリゴン取囲みボックス周辺長）／（取囲まれたポリゴン点の数）
例
バックグラウンドオブジェクト上に二つのオブジェクトを有する１頁の一部に対するベクトルマップトラッピングの一例を図１−５に示してある。より詳細に説明すると、図１はバックグラウンドオブジェクトＣを有するタイル上の二つのポリゴンオブジェクトＡ，Ｂの一部を示している（バックグラウンドオブジェクトはそのタイルを完全にカバーする頁又はオブジェクトとすることが可能である）。図１は、どの様にしてこれらのオブジェクトが印刷されるか、即ちオブジェクトＢがオブジェクトＡの上側にプリントされ、且つオブジェクトＡ，Ｂの両方がオブジェクトＣの上側にプリントされるかを示している。
【００２５】
図２はポリゴン輪郭セグメントＣA，ＣBを示しており、図１のタイル上に重ね合わせられた任意の７×７ベクトルマップグリッド上に描画された二つのオブジェクトＡ，Ｂのエッジを有している。バックグラウンドオブジェクトＣはベクトルマップ境界ＣCによって表わされている。
【００２６】
図３は図２のタイルのベクトルマップ表示を示している。ポリゴン輪郭セグメントＣA，ＣBは、影線を付けたセルとしてベクトルマップ内において視覚的に表現されている。好適実施例においては、１個のセルと接触する各輪郭セグメントＣA，ＣBからの各エッジセグメントへのポインタがそのセルに対して維持されているエッジリスト内にエンタされる。（注意すべきことであるが、ベクトルマップのグラフィック表示が図示されているが、同一の情報を捕獲するために任意の所望のデータ構造を使用することが可能である。例えば、単に、少なくとも１個のエッジセグメントを有するセルに対するセル番号及びそのセル内のエッジセグメントの数を追従するルックアップテーブルデータ構造を使用することが可能である。その他のデータ構造、例えばアレイ、リンクさせたリストなどを使用することも可能である。）又、そのエッジカウントが高すぎる場合には、任意のセルを細分化することが可能であり、その場合には、エッジに対してポイントするリーフノード（ｌｅａｆ  ｎｏｄｅ）を有するカッドツリー（ｑｕａｄ−ｔｒｅｅ）を使用することが可能である。しかしながら、このことは必須なものではない。
【００２７】
図示した例においては、図３における二つの影線の付けたセル（３，４）及び（４，４）がセルのエッジリスト内にエンタさせた二つを超えるエッジを有する唯一のセルであって、且つその場合には、交差テストが必要とされる。残りのセル内のエッジは交差を有するものでないことを容易に見極められる。なぜならば、それらは各セルのエッジリストにおけるエッジ数から決定されるように、それらのセルを共用するものではないからである（即ち、エッジ数が２未満である場合には、セルは交差するポリゴン線を有することは不可能である）。図３から容易に理解されるように、タイルをベクトルマップとして表示することによって、交差する輪郭セグメントの決定は、複雑なデータ処理又は大きなメモリ条件なしで達成される。
【００２８】
オブジェクトの輪郭を定義する輪郭セグメントの交差は、一つのオブジェクトが別のオブジェクトの「上側」にあることを表わし、且つどちらのエッジセグメントが隠され、従って印刷されるものではないかを決定するための処理を必要とする。トラッピングは隠されることのないエッジに対してのみ適用される。交差を処理するために、ポリゴン輪郭セグメントに対する全ての開始点及び終了点のリストが維持されている。交差するエッジがスプリット即ち分割する場合に、新たな輪郭セグメントが発生される。好適実施例においては、ポリゴンエッジがベクトルマップセル内に描画される場合に、既に該セル内にある何れかのエッジとの交差が各セルのエッジリストを検査することによって決定される。二つの交差するエッジがスプリット即ち分割されて四つの新たなエッジを生成し且つその結果発生する輪郭セグメントは、開始点及び終了点リスト内へ二つの新たな輪郭開始点及び終了点を挿入することによって追跡される。
【００２９】
例えば、図４は隠された線の決定及び除去を示した１頁のタイルのベクトルマップ表示を示している。輪郭セグメントＣAが最初に描画されるものと仮定する。それは＜１，２＞の開始−終了点を有している。次いで、輪郭セグメントＣBが描画され、それは開始点＜３＞を有している。しかしながら、輪郭セグメントＣBの描画が輪郭セグメントＣAとの交差部に到達すると、輪郭セグメントＣBはセグメント＜３，４＞と＜６，８＞とにスプリット即ち分割され、一方輪郭セグメントＣAはセグメント＜１，７＞と＜５，２＞とに分割される。新たな開始点＜５＞，＜６＞及び新たな終了点＜４＞，＜７＞が開始−終了点リスト内へエンタされる。
【００３０】
図示した例においては、エッジスプリット（分割）によって作成された輪郭セグメント及び描画された輪郭セグメントの「左側」においてそれらに接続されたセグメントは、現在の輪郭セグメントのオブジェクトがオーバープリント即ち上側に印刷されない場合には隠されることとなる（このことは、ポリゴンの内部が現在のエッジの左側であると仮定している）。ポリゴンが図２におけるベクトルマップの一部をカバーする場合には、そのベクトルマップにおける前にエンタした輪郭セグメントが隠されるものとしてマーク付けが行われ且つそのベクトルマップをクリアすることが可能である。例えば、図４における点線で示した輪郭セグメント＜１，７＞は第二ポリゴンオブジェクトＢの下側に隠されている（図１参照）。それは見えておらず且つその様なものとしてフラッグが立てられ、且つ開始点及び終了点が開始−終了リストから削除される。
【００３１】
次いで、図４におけるベクトルマップを、各見えている輪郭セグメントをトレースし且つそれに沿ってトラップを発生することによってトラッピングを行う。輪郭セグメントは、輪郭セグメント開始−終了リスト内のその開始からその終了までトレースする（これはエッジを有するセルに対するベクトルマップのスキャニングに対する代替物である）。好適実施例においては、トラップ関数は、トラップポリゴンＣTが既知の態様でオブジェクト輪郭と共通のエッジを共用するように表わされたトラップポリゴンＣTからなるシーケンス、及びオブジェクト輪郭の左側及び右側上のインクからなるカラーを有している。カラーの外側は、エッジを有するセルに遭遇するまで、タイルマップの行又は列に沿ってスキャニングすることによって決定される。最近設エッジのカラーが使用される。図５は１頁のタイルのベクトルマップ表現を示しており、適用したトラップポリゴンＣTを示している。所望により、その他のトラッピング関数を使用することも可能である。
【００３２】
好適実施例においては、トラップポリゴンをベクトルマップ内に描画させ且つ該ポリゴン及び隣接するセル（必要な場合）を含むセルが、元のオブジェクトに対して上述したような態様で、エッジに対してチェックされて、該トラップポリゴンがその他の輪郭セグメントからのエッジ又はトラップポリゴンと交差するか否かを決定する。セル寸法は最大トラップ幅（トラップポリゴンの幅）よりも大きいものと仮定される。交差するポリゴンは既知の態様で交差部を除去すべく再整形される。
【００３３】
注意すべきことであるが、トラップポリゴンの発生及びベクトルマップにおけるエッジ描画は、単一のステップに結合させることが可能であり、従って、トラップポリゴンはエッジと共に発生され且つベクトルマップ内へエンタされる。この場合には、隠されたエッジに対するトラップポリゴンは廃棄され且つトラップポリゴン−エッジ交差が検知される場合にはトラップポリゴンが再整形される。
ベクトルマップ表示はベクトルマップ及びベクトルマップを作成することに関連するあるオーバーヘッドのために付加的なメモリを必要とするが、ベクトルマップの分解能はこれらの両方の問題点の影響を最小とするために、タイル毎に動的に選択することが可能である。例えば、タイルが数個のオブジェクトを有する場合には、ベクトルマップに対して非常に低い分解能（数個のセル）を使用することが可能であり、且つタイルが多数のオブジェクト又はキャラクタを有する場合には、より高い分解能をベクトルマップに対して使用することが可能である。具体化
本発明は、ハードウエア又はソフトウエア、又は両方の組合わせで具体化することが可能である。しかしながら、好適には、本発明は、各々が少なくとも１個のプロセサと、データ格納システム（揮発性及び非揮発性メモリ及び／又は格納要素を含む）、少なくとも１個の入力装置、少なくとも１個の出力装置を有するプログラム可能なコンピュータ上で稼動するコンピュータプログラムの形態で具体化される。プログラムコードが入力データへ付与されて、本明細書に記載した機能を実行し且つ出力情報を発生する。その出力情報は既知の態様で一つ又はそれ以上の出力装置へ付与される。
【００３４】
各プログラムは、好適には、ハイレベル手順又はオブジェクト指向型プログラミング言語で具体化されて、コンピュータシステムと通信を行う。しかしながら、該プログラムは、所望により、アッセンブリ又はマシン言語で具体化することが可能である。何れの場合においても、該言語はコンパイル型又はインタプリタ型の言語とすることが可能である。
【００３５】
各この様なコンピュータプログラムは、好適には、格納媒体又は装置が本明細書に記載した手順を実行するコンピュータによって読取られる場合に、コンピュータを所定の形態とさせ且つ動作するための汎用又は特別目的のプログラム可能なコンピュータによって読取り可能な格納媒体又は装置（例えば、ＲＯＭ又は磁気ディスケット）上に格納される。本発明システムは、コンピュータプログラムで所定の形態とされるコンピュータによって読取り可能な格納媒体として具体化することも可能であり、その場合には、その様な形態とされる格納媒体は、コンピュータをして、特定の且つ予め定めた態様で動作を行わせて本明細書に記載した機能を実行させる。
【００３６】
以上、本発明の具体的実施の態様について詳細に説明したが、本発明は、これら具体例にのみ限定されるべきものではなく、本発明の技術的範囲を逸脱することなしに種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【図１】  カラーを付けたバックグラウンド上の二つのポリゴンオブジェクトの一部を有するタイルを示した概略図。
【図２】  画像のタイル上に重ね合わせたベクトルマップグリッド上に描画した図１に示した二つのオブジェクトの一部を有するポリゴン輪郭セグメントの概略図。
【図３】  図２のタイルのベクトルマップ表示の概略図。
【図４】  隠れた線の決定及び除去を示した１頁の１個のタイルのベクトルマップ表示を示した概略図。
【図５】  適用したトラップを示した１頁の１個のタイルのベクトルマップ表示を示した概略図。
【符号の説明】
Ａ，Ｂ  ポリゴンオブジェクト
Ｃ  バックグラウンドオブジェクト
ＣA，ＣB  ポリゴン輪郭セグメント
ＣC  ベクトルマップ境界
ＣT  トラップポリゴン
【図１】
0004624502.tif 000002
【図２】
0004624502.tif 000003
【図３】
0004624502.tif 000004
【図４】
0004624502.tif 000005
【図５】
0004624502.tif 000006