(57)【特許請求の範囲】
【請求項１】
オブジェクトベースラスタ化イメージを充填する装置であって、
画像メモリを用いることなくオブジェクトのピクセルエッジポジションデータと注目ラスターラインのカレントピクセルポジションデータを比較する比較手段と、
前記比較手段による比較に基づき、オブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替える手段と、
前記オブジェクトのフラグを調べ、ＯＮフラグを持ちオブジェクトの最上位優先レベルを持つオブジェクトに対応するカレントピクセルのためのデータを選択することによりカレントピクセルのデータを生成する手段とを有することを特徴とする装置。
【請求項２】
前記切り替える手段は、前記比較結果に基づき、他のオブジェクトのＯＮ、ＯＦＦフラグが影響を受けないように、特定のオブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替えることを特徴とする請求項１記載の装置。
【請求項３】
スキャンラインとアウトラインフラグメントの交差のエッジ計算を行い、優先レベルとフラグメント交差のピクセルポジションの分類されたリストを作成する手段をさらに有することを特徴とする請求項１または２記載の装置。
【請求項４】
オブジェクトを各々ラスターラインに現れるオーダーに分類する手段をさらに有することを特徴とする請求項１乃至３のいずれか１項に記載の装置。
【請求項５】
前記切り替える手段は、トグルラッチを切り替えることにより、オブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替えることを特徴とする請求項１乃至４のいずれか１項に記載の装置。
【請求項６】
前記生成する手段は、前記比較結果に基づき、エッジポジションのオブジェクトの優先レベルが出力されているレベルより低い場合、レベル出力を変更せず、エッジポジションのオブジェクトの優先レベルが出力されているレベルより高い場合、エッジポジションのオブジェクトのレベルに変更し、エッジポジションのオブジェクトのレベルが最上位優先レベルと同じ時に、カレントレベルより低い最上位動作レベルに変更する手段を含むことを特徴とする請求項１乃至５のいずれか１項に記載の装置。
【請求項７】
前記生成する手段により生成されたカレントピクセルのデータに基づき表示を行う手段をさらに有することを特徴とする請求項１乃至６のいずれか１項に記載の装置。
【請求項８】
前記生成する手段により生成されたカレントピクセルのデータに基づき印刷を行う手段をさらに有することを特徴とする請求項１乃至７のいずれか１項に記載の装置。
【請求項９】
オブジェクトベースラスタ化イメージを充填する方法であって、
画像メモリを用いることなく注目ラスターラインのカレントピクセルポジションデータとオブジェクトのピクセルエッジポジションとを比較するステップと、
前記比較するステップによる比較に基づきオブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替えるステップと、
前記オブジェクトのフラグを調べ、ＯＮフラグを持ちオブジェクトの最上位優先レベルを持つオブジェクトに対応するカレントピクセルのためのデータを選択することによりカレントピクセルのデータを生成するステップとを有することを特徴とする方法。
【請求項１０】
前記切り替えるステップは、前記比較結果に基づき、他のオブジェクトのＯＮ、ＯＦＦフラグが影響を受けないように、特定のオブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替えることを特徴とする請求項９記載の方法。
【請求項１１】
スキャンラインとアウトラインフラグメントの交差のエッジ計算を行い、優先レベルとフラグメント交差のピクセルポジションの分類されたリストを作成するステップをさらに有することを特徴とする請求項９または１０記載の方法。
【請求項１２】
オブジェクトを各々ラスターラインに現れるオーダーに分類するステップをさらに有することを特徴とする請求項９乃至１１のいずれか１項に記載の方法。
【請求項１３】
前記切り替えるステップは、トグルラッチを切り替えることにより、各オブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替えることを特徴とする請求項９乃至１２のいずれか１項に記載の方法。
【請求項１４】
前記生成するステップは、前記比較結果に基づき、エッジポジションのオブジェクトの優先レベルが出力されているレベルより低い場合、レベル出力を変更せず、エッジポジションのオブジェクトの優先レベルが出力されているレベルより高い場合、エッジポジションのオブジェクトのレベルに変更し、エッジポジションのオブジェクトのレベルが最上位優先レベルと同じ時に、カレントレベルより低い最上位動作レベルに変更するステップを含むことを特徴とする請求項９乃至１３のいずれか１項に記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、オブジェクト・ベース・グラフィック・システムに関するものであり、特に、オブジェクト・ベース・ラスター化イメージを、そのイメージをビデオ・ディスプレイ上に或いは印刷機能を用いて表示する前に、充填することに依って隠れている表面の除去を与える方法と装置を開示するものである。
【０００２】
【従来の技術】
ほとんどのオブジェクト・ベース・グラフィック・システムは、ページまたはスクリーンのピクセル・ベース・イメージを保持するためにフレーム・ストアまたはページ・バッファを用いている。オブジェクトのアウトラインが、計算され、充填されて、フレーム・ストアに書き込まれている。２次元グラフィックの場合、他のオブジェクトの前に現れるオブジェクトは、バックグラウンド・オブジェクトの後にフレーム・ストアに単純に書き込まれて、バックグラウンドをピクセルごとの基準で置換している。これは“ペインターペインターのアルゴリズム”として広く知られている周知の技術である。イメージは、オブジェクト・オーダーで、最後のオブジェクトから最初のオブジェクトにかけて計算される。しかし、ラスター・ディスプレイのリアルタイム・イメージ生成は、ラスター・オーダーのイメージの計算を要求する。これは、各々スキャン・ラインがそれが到達される時に計算されなければならなくて、なおかつ、各々スキャン・ラインと各々オブジェクト・ラインの交差ポイントが計算され次に充填されることを要求していることを意味している。
【０００３】
【発明が解決しようとする課題】
ページ・バッファよりむしろライン・バッファを使用し、ペインターのアルゴリズムをスキャン・ライン内部で使用してオブジェクトを充填することができるが、リアルタイムのイメージ生成は、ビデオ・データ・レートでは、この方法を使用すると高価になる。
【０００４】
オブジェクトをイメージにオーバーレイして、フレームまたはライン・ストアを必要とせずに、ラインごとの基準で充填されることができる手段を用いて前述の難しさを克服することが、本発明の目的である。
【０００５】
【課題を解決するための手段】
上記目的を達成するために本発明は次の構成を有する。
【０００６】
オブジェクトベースラスタ化イメージを充填する装置であって、
画像メモリを用いることなくオブジェクトのピクセルエッジポジションデータと注目ラスターラインのカレントピクセルポジションデータを比較する比較手段と、
前記比較手段による比較に基づき、オブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替える手段と、
前記オブジェクトのフラグを調べ、ＯＮフラグを持ちオブジェクトの最上位優先レベルを持つオブジェクトに対応するカレントピクセルのためのデータを選択することによりカレントピクセルのデータを生成する手段とを有する。
【０００７】
更に好ましくは、前記切り替える手段は、前記比較結果に基づき、他のオブジェクトのＯＮ、ＯＦＦフラグが影響を受けないように、特定のオブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替える。
【０００８】
更に好ましくは、スキャンラインとアウトラインフラグメントの交差のエッジ計算を行い、優先レベルとフラグメント交差のピクセルポジションの分類されたリストを作成する手段をさらに有する。
【０００９】
更に好ましくは、オブジェクトを各々ラスターラインに現れるオーダーに分類する手段をさらに有する。
【００１０】
更に好ましくは、前記切り替える手段は、トグルラッチを切り替えることにより、オブジェクトのレベルに対応するＯＮ、ＯＦＦフラグを切り替える。
【００１１】
更に好ましくは、前記生成する手段は、前記比較結果に基づき、エッジポジションのオブジェクトの優先レベルが出力されているレベルより低い場合、レベル出力を変更せず、エッジポジションのオブジェクトの優先レベルが出力されているレベルより高い場合、エッジポジションのオブジェクトのレベルに変更し、エッジポジションのオブジェクトのレベルが最上位優先レベルと同じ時に、カレントレベルより低い最上位動作レベルに変更する手段を含む。
【００１２】
更に好ましくは、前記生成する手段により生成されたカレントピクセルのデータに基づき表示を行う手段をさらに有する。
【００１３】
更に好ましくは、前記生成する手段により生成されたカレントピクセルのデータに基づき印刷を行う手段をさらに有する。
【００１４】
【実施例】
まず図１を見ると、イメージ・フレーム・ストアがないことを特徴とする、リアルタイム・オブジェクト・ベース・グラフィック・システム１のデータ・フロー図が図示されている。システム１は、ユーザが、図表、イメージ・スキャナー、イメージのデータベース、または類似機能の何れかを用いて種々のイメージを選択できることを可能にする、イメージ生成ワークステーション２を一般的に搭載している。ユーザは、イメージをオブジェクトに分割し且つこれらのオブジェクトのページ・ディスプレイ・リストを生成するために動作するプロセッサー４にコマンド・コンソール３を経由して指定コマンドを入力することができる。
【００１５】
前述のように、イメージ・フレーム・ストアが使用できる時は、オブジェクトは、全体のイメージを形成するために、１つづつの基準でフレーム・ストアに記憶される必要があるだけである。しかし、リアルタイム・イメージ生成の場合、該メモリ内部でピクセル・データをオーバーライトするだけでなく、計算し記憶するために要求されるプロセスが、非常に大きくなるので、低コスト・システムに適していない。
【００１６】
特に、最終的なイメージのオブジェクトの各々がラインごとの基準で処理されることが要求される。これは、イメージの各々オブジェクトに対してオブジェクト（オブジェクト・フラグメント）５の部分の形成、変換、拡大縮小に依って最初に実施される。種々のサブオブジェクトは、そこで、それらがディスプレイの各々ラスター・ラインに現れるオーダーに分類される６。イメージの全てのオブジェクト・フラグメント間の交差を決定するエッジ計算７が行われるので、イメージは、エッジ・ピクセル・データ、およびイメージが各々エッジ横断後に変わるカラー・レベルに依って表されることだけを必要とすることになる。このデータは、次に、エッジ・ピクセル・データとカラー・レベルを用いて、なおかつ、ディスプレイ１０と同期して、イメージのラスター・ラインの各々ピクセルに対してピクセル・レベル・データを出力する、充填計算器８の出力になる。このピクセル・レベル・データは、次に、指定カラー・インフォメーションをＲＧＢ（赤、緑、青）またはＣＹＭＫ（青緑、深紅、黄、黒）または他のカラー・データ・フォーマットの状態でビデオ・ディスプレイまたはプリンタのようなイメージ・ディスプレイ１０に各々出力するカラー設定デバイス９の入力になる。
【００１７】
図１に図示されているように、データ・フロー・ステージ５，６，７，８は、これと共に同時に提出されている、１９９３年４月２９日のオーストラリア特許出願ＮｏＰＬ２１４７に開示されているようなもの、且つここでクロス・リファレンスに依って包合されている開示のように、シングル・リアルタイム・オブジェクト・グラフィック・プロセッサー１１と組み合わされることができる。
【００１８】
図２〜図６は、いま説明されたばかりの“ラスター化”と呼ばれる、イメージ生成プロセスを示している。このケースで、イメージ１２は、第１オブジェクトとして動作するバックグラウンド１３、第２オブジェクトとして動作する文字“Ａ”１４、第３オブジェクトとして動作する長方形１６、第４オブジェクトとして動作する円１５に依って形成されている。
【００１９】
図２は、曲線のアウトラインの各々フラグメントと各々曲線フラグメントの優先レベルを説明する数字のシリーズであるイメージ１２のアウトライン・インフォメーションを示している。優先レベルは、各々オブジェクトが最終イメージでとるレベルおよびオブジェクトが相互にオーバーレイする状態に相応してアナログになる。これは、ペインターのアルゴリズムの使用に依って構成される配置を補足している。また、図２に、図３、４、５を引用しながら用いられているシングル・スキャン・ラインを示すセクション・ライン１８−１８が見られる。
【００２０】
図３に見られるように、各々スキャン・ラインとアウトライン・フラグメントの交差のエッジ計算が包合されている。これは、優先レベルと共に、各々フラグメント交差のピクセル・ポジションの分類されたリストになる。図３は、イメージのシングル・スキャン・ラインを示し、なおかつ、優先レベルが図３の層の各々の高さに依って表されている図２のライン１８−１８を経由する断面を示している。
【００２１】
図４では、充填される領域が生成されている。これらの領域は“偶数／奇数の規則”に依って充填される。これは、現れる第１交差がカラーの充填をＯＮにすると、第２交差が充填をＯＦＦにし、次に、第３が充填をＯＮにし、以降同様に行われる。この充填方法が、文字Ａ１４のように、オブジェクトのホールを可能にし、バックグラウンド１３がそこに現れることを可能にする。
【００２２】
次に、図５に見られるように、隠れていた表面が除去される。高い優先順位の他のオブジェクトに依って妨げられていたオブジェクトが、除去されるので、変動するピクセル・カラー・レベルのブロックに依って分割されるシングル・スキャン・ラインに適したデータのストリングを生成する。
【００２３】
図６は、円１５が最上位の優先順位で且つバックグラウンド１３が最下位の優先順位で印刷または表示される最終イメージ１２を示している。
【００２４】
本発明は、図４と図５の結果が行われる方法と装置に特に関連している。
【００２５】
ここで図７を見ると、ピクセル・エッジ・ポジション・データ２１とカラー・レベル・データ２４をエッジ計算器７から図１に見られるようにして受け取る、充填計算器２０が図示されている。ラスター・ラインのピクセル・ポジション２２に関連する更なる入力は、図１のディスプレイのように、ディスプレイから同期して来るので、ピクセル・データは同期した状態でその出力になることができる。各々エッジのレベル・データ２４は、デコーダ３０を用いて完全にデコードされて、個々のビット・レベル・データ２５を、１つのラッチがデコードされるレベル・データ２５の各々値に相応している、複数のトグル・ラッチ２６の入力に出力する。
【００２６】
コンパレータ２３は、ピクセル・エッジ・ポジション２１とライン２２のピクセル・ポジションを比較するために与えられている。ピクセル・エッジ値がマイナスの場合またはそれがラインのピクセル・ポジションの値と同じ時に、トグル・ラッチ２６が同時にトリガされる。これは、他のラッチの全てが影響を受けない状態で、特定のオブジェクトのレベルに対応するトグル・ラッチを切り替える。これが前述の偶数／奇数の規則を実現する。トグル・ラッチ２６の出力は、ディスプレイで今動作状態のオブジェクトの全てに対応している。このオペレーションは、図４に与えられているレベル充填と同じである。
【００２７】
優先順位エンコーダ２８はトグル・ラッチ２６の出力に接続していて且つ表示されている最上位レベル出力を選択する。これは次にエンコードされ充填レベル２９として出力される。従って、優先エンコーダ２８は図５に見られるように隠れている表面の除去を実施する。例えば、ちょうどトリガされたレベルの優先レベルが優先エンコーダ２８に依って出力されるレベルより低い場合、カラー・レベル出力２９は変更されない状態のままである。代わりに、ちょうどトリガされたレベルが優先エンコーダに依って出力されたレベルより高い場合、レベル出力２９はちょうどトリガされたレベルのものに変更される。また、ちょうどトリガされたレベルが今の最上位優先レベルと同じ時に、出力はカレント・レベルより低い最上位動作レベルに変わる。これが、第２オブジェクトが高い優先順位をもち且つ第１をオーバーレイすることが意図されている、２つのオブジェクト間のエッジの変化に基づく出力イメージの変更を行う。出力レベル・データ２９は、次にディスプレイのラスター・ラインのピクセル・ポジションに表示されるカラーを選択するために用いられる。
【００２８】
ここで図８を見ると、充填計算器４０の好まれる実施態様は、カレント・ラインのオブジェクト・エッジのピクセル・ポジションが入力となり且つエッジ・ポジション・データ（ＥＰ）４１の１６ビットと充填レベル（ＦＬ）４９の６ビットを有している状態で図示されている。ディスプレイと同期しているピクセル・クロック（ＰＣＬＫ）４３は、ピクセルの初期化数４４と共に、コンパレータ４６の“Ａ”入力の入力となる今のラスター・ラインのカレント・ピクセル・ポジションをピクセル・カウンター４５から出力する、ピクセル・カウンター４５に入力する。エッジ・ポジション・データ（ＥＰ）４１は、ＮＯＲゲート４８の１つの入力に接続されている出力４７をもつコンパレータ４６の“Ｂ”入力に与えられる。ＮＯＲゲート４８もピクセル・データ４１の最上位ビット（ＥＰ１５）をもつ入力である。ＮＯＲゲート４８は、トグル・ラッチとして接続されている６４Ｊ−Ｋフリップフロップ５１のバンクのクロック入力５２に出力する。フリップフロップ５１の各々は、６−６４デコーダ５０を経由して送られる１つのデコードされた充填レベル４９に依ってイネーブルにされる。フリップフロップ５１がクロック入力５２に依ってトリガされる時に、イネーブルされたレベルに対応するこれらのフリップフロップは、ステートを変更（トグル）して、偶数／奇数の規則を実現する。トグル・フリップフロップ５１はライン同期５６に依って各々ラインの開始位置でリセットされる。トグル・フリップフロップ５１の出力は、最上位の６４入力ステートがその出力ステートに基づいて表されることだけ可能にする、優先順位回路５３に接続されている。この“最上位ステート”は、次に、エンコーダ５４に依って６ビット・バイナリ値にエンコードされて、出力レベル５５を与える。
【００２９】
出力レベル・データ１５は、そこで、カラー・ルックアップ・テーブル（図示されていないが周知の技術である）の入力となり、表示されるピクセルのために実際のカラー・データの２４−ビット・ブロックを出力することができる。
【００３０】
図７と図８の充填計算器は、ペインターのアルゴリズムと同等の結果が、フル・ページ・ストアに見られる必要な量と時間のロスを招かずに達成される手段を与える。前述のオーストラリア特許出願ＮｏＰＬ２１４７で説明された特定の実施例の場合、グラフィック・オブジェクトは、ベジェ・スプライン・ベース・オブジェクト・データと比較される時に、それらの単純な数学的表現から、エッジ計算７までの高速処理を可能にする、２次多項式フラグメントとして処理される。しかし、本発明は、２次多項式フラグメントで動作するグラフィック・システムに限定されない。
【００３１】
前述の説明は本発明の数多くの実施態様を述べていて、なおかつ、当業者にとって明かな変更が、本発明の範囲から逸脱せずに実施されることができる。
【００３２】
【発明の効果】
オブジェクトをイメージにオーバーレイして、フレームまたはライン・ストアを必要とせずに、ラインごとの基準で充填されることができる手段を用いることにより、オブジェクト・ベース・ラスター化イメージの隠れている表面の除去を安価に行うことができる方法とその装置を提供することができる。
【図面の簡単な説明】
【図１】好まれる実施態様を包合するオブジェクト・ベース・グラフィック・システムの略ブロック図である。
【図２】数多くのオブジェクトから形成されるイメージのアウトラインを示す図である。
【図３】優先順位で見られる時の図２のイメージを示す図である。
【図４】オブジェクトの各々が完全にカラー化されている、図３と類似の図である。
【図５】隠れていた表面が除去された後の図４と類似の図である。
【図６】図５のイメージの図である。
【図７】本発明の単純な実施態様をしめす図である。
【図８】オブジェクト・ベース・グラフィック・システムに使用するために構成されている好まれる実施態様を示す図である。
【符号の説明】
１  リアルタイム・オブジェクト・ベース・グラフィック・システム
２  イメージ生成ワークステーション
３  ユーザ・コンソール
４  オブジェクトとしてイメージを形成
５  オブジェクト・フラグメントの形成、変換、拡大縮小
６  オブジェクト・フラグメントの分類
７  エッジ計算
８  充填計算
９  カラー設定
１０  表示（印刷、ビデオ）
２１  エッジのピクセル・ポジション
２２  ラインのピクセル・ポジション
２３  コンパレータ
２４  レベル・データ
２６  トグル・ラッチ
２８  優先順位エンコーダ
２９  レベル出力
３０  デコーダ
４１  エッジ・ポジション（ＥＰ）
４３  ピクセル・クロック（ＰＣＬＫ）
４４  ピクセルの初期化Ｎｏ．
４５  ピクセル・カウンター
４９  充填レベル（ＦＬ）
５０  ６−６４デコーダ
５１  トグル・フリップフロップ
５３  優先順位
５４  ６４−６エンコーダ
５５  レベル出力
５７  ライン同期
【図１】
0003564118.tif 000002
【図２】
0003564118.tif 000003
【図３】
0003564118.tif 000004
【図４】
0003564118.tif 000005
【図５】
0003564118.tif 000006
【図６】
0003564118.tif 000007
【図７】
0003564118.tif 000008
【図８】
0003564118.tif 000009