(57)【要約】      （修正有）【課題】既存装置における非効率性を削減するグラフィックスシステムを提供する。【解決手段】複数の優先度を付けたオブジェクトを受信し、受信したオブジェクトが関連付けられたオブジェクトグループの一部を形成するかどうかを検出し、１以上のオブジェクトグループが完全に形成されたかどうかを決定し、形成されたオブジェクトグループを優先度に基づいてレンダリングするための出力工程を備える。【選択図】図３
2004295900.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトグループを、複数の受信したオブジェクトから形成するための方法であって、
前記受信したオブジェクトを記述するデータを少なくとも一つの検出スキームへ送信する工程であって、各検出スキームは、優先度と関連づけられたオブジェクトグループタイプとを有し、前記受信したオブジェクトが前記関連づけられたオブジェクトグループタイプのオブジェクトグループの一部を形成するかどうかを検出するように動作する工程と、
前記少なくとも一つの検出スキームから、前記受信したオブジェクトが前記オブジェクトグループの一部を形成するかどうかの通知を受信する工程と、
１以上の前記オブジェクトグループが、完全に形成されたかどうかを決定する工程であって、少なくとも部分的に形成されたオブジェクトグループがリストを形成する工程と、
完全に形成されたオブジェクトグループを前記優先度に基づいてレンダリングのために出力する工程と
を、前記受信したオブジェクトのそれぞれについて備えることを特徴とする方法。
【請求項２】
前記完全に形成されたオブジェクトグループが、最も優先度の高い前記検出スキームと関連づけられたタイプの前記リスト内のオブジェクトグループである場合に、前記出力工程では前記完全に形成されたオブジェクトグループが出力されることを特徴とする請求項１に記載の方法。
【請求項３】
前記受信したオブジェクトは、関連するオブジェクトグループタイプを有する検出スキームへ送信され、前記受信したオブジェクトは、前記関連づけられたオブジェクトグループタイプのオブジェクトグループの潜在的な構成要素であり、前記検出スキームは前記リスト内のオブジェクトグループを有することを特徴とする請求項１に記載の方法。
【請求項４】
前記オブジェクトグループの部分を形成しない受信したオブジェクトをレンダリングのために出力する工程をさらに備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記完全に形成されたオブジェクトグループのオブジェクトが少なくとも１つ出力されている場合に、出力されていない１以上のオブジェクトグループの部分を形成する以前に受信したオブジェクトをレンダリングするために出力する工程をさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記以前に受信したオブジェクトが部分を形成するオブジェクトグループのタイプと関連づけられた検出スキームの属性に応じて、（i）個別に又は（ii）グループとしてレンダリングするために前記以前に受信したオブジェクトが出力されることを特徴とする請求項５に記載の方法。
【請求項７】
複数の受信オブジェクトからオブジェクトグループを形成するグラフィックレンダリングシステムであって、
複数の検出スキームであって、各検出スキームが優先度及び関連づけられたオブジェクトグループタイプを有し、前記関連づけられたオブジェクトグループタイプのオブジェクトグループの部分を形成するオブジェクトであるかを検出するように動作する複数の検出スキームと、
受信したオブジェクトを記述するデータを少なくとも一つの検出スキームへ送信し、前記少なくとも一つの検出スキームから、前記受信されたオブジェクトが前記オブジェクトグループの一部を形成するかどうかの通知を受信し、少なくとも部分的に形成されたオブジェクトグループがリストを形成する場合に１以上の前記オブジェクトグループが完全に形成されたかどうかを決定し、前記優先度に基づいて完全に形成されたオブジェクトグループをレンダリングモジュールへ送信するためのマネージングモジュールと
を備えることを特徴とするグラフィックレンダリングシステム。
【請求項８】
前記完全に形成されたオブジェクトグループが、最も優先度の高い前記検出スキームと関連づけられたタイプの前記リスト内のオブジェクトグループである場合に、前記マネージングモジュールは、前記完全に形成されたオブジェクトグループを前記レンダリングモジュールへ送信することを特徴とする請求項７に記載のグラフィックレンダリングシステム。
【請求項９】
前記受信したオブジェクトが、関連するオブジェクトグループタイプを有する検出スキームへ送信され、前記受信したオブジェクトが、前記関連づけられたオブジェクトグループタイプのオブジェクトグループの潜在的なメンバーであり、検出スキームが前記リスト内のオブジェクトグループを有することを特徴とする請求項７に記載のグラフィックレンダリングシステム。
【請求項１０】
前記マネージングモジュールはさらに、前記オブジェクトグループの部分を形成しない受信したオブジェクトを前記レンダリングモジュールへ送信することを特徴とする請求項７に記載のグラフィックレンダリングシステム。
【請求項１１】
前記マネージングモジュールは、以前に受信したオブジェクトを前記レンダリングモジュールへ送信し、前記以前に受信したオブジェクトはレンダリングされていない１以上のオブジェクトグループの部分を形成し、前記完全に形成されたオブジェクトグループの少なくとも１つはレンダリングされていることを特徴とする請求項７に記載のグラフィックレンダリングシステム。
【請求項１２】
前記以前に受信したオブジェクトが一部を形成するオブジェクトグループのタイプと関連づけられた検出スキームの属性に応じて、前記以前に受信されたオブジェクトは（i）個別に又は（ii）グループとして前記レンダリングモジュールへ送信されることを特徴とする請求項１１に記載のグラフィックレンダリングシステム。
【請求項１３】
オブジェクトグループを、複数の受信したオブジェクトから形成するためのコンピュータプログラムを記録したコンピュータで読み取り可能な記録媒体を含むコンピュータプログラム製品であって、前記コンピュータプログラムは、
前記受信したオブジェクトを記述するデータを少なくとも一つの検出スキームへ送信するコードであって、各検出スキームは、優先度と、関連づけられたオブジェクトグループタイプとを有し、前記受信したオブジェクトが、前記関連づけられたオブジェクトグループタイプのオブジェクトグループの一部を形成するかどうかを検出するように動作するコードと、
前記少なくとも一つの検出スキームから、前記受信したオブジェクトが前記オブジェクトグループの一部を形成するかどうかの通知を受信するコードと、
１以上の前記オブジェクトグループが、完全に形成されたかどうかを決定するコードであって、少なくとも部分的に形成されたオブジェクトグループはリストを形成するコードと、
完全に形成されたオブジェクトグループを前記優先度に基づいてレンダリングのために出力するコードと
を、受信したオブジェクトのそれぞれについて備えることを特徴とするコンピュータプログラム製品。
【請求項１４】
前記完全に形成されたオブジェクトグループが、最も優先度の高い前記検出スキームと関連づけられたタイプの前記リスト内のオブジェクトグループである場合に、前記出力するコードは、前記完全に形成されたオブジェクトグループを出力することを特徴とする請求項１３に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オブジェクトレンダリングシステムにおけるオブジェクトのマネジメントに概ね関連し、より詳細には、オブジェクトレンダリングシステムにおけるグラフィカルオブジェクト検出スキームのマネージメントに関連する。
【背景技術】
【０００２】
レンダリングは、グラフィックオブジェクトを画素に変換する処理である。グラフィックレンダリングシステムは、基本的にペインターズアルゴリズムスタイル(painters algorithm style)のレンダリング手法を利用するが、かかるスタイルでは、各オブジェクトが到達した順に（as it arrives）フレームバッファに描画される。他のグラフィックレンダリングシステムは２段階手法を利用する。ここでグラフィックレンダリングシステムは、まず、入力される全てのオブジェクトを幾つかの中間フォーマットに各ページについて変換する。次に、同時に走査線をレンダリングする(the second stage renders a scanline at a time.)。
【０００３】
グラフィックレンダリングシステムのタイプを問わず、アプリケーションプログラムから受信するグラフィックコマンドのいくつかの性質により、効率の問題を被ることとなる。例えば、一般的な描画アプリケーションプログラムは、スムーズなグラデーション（gradient fill）の印象を与えるために、わずかに異なる単調な色（slightly different flat colour）を有する隣接し重なり合った長方形のグループとして、グラデーションをグラフィックレンダリングシステムに送信される。この場合、オリジナルのオブジェクトの性質に忠実なものにはなるが、グラフィックオブジェクトは冗長なデータが多く含まれることとなる。
【０００４】
上述の非効率性を削減する試みにおいて、より複雑なグラフィックオブジェクトと結合されるであろうシンプルなグラフィックオブジェクトを検出し、そのようなグラフィックオブジェクトを、オブジェクトグループと結合し、それによって冗長なデータを削減すると共に、ラスタオペレーション(raster operations)の数を減少させるものが提案されている。
【０００５】
オブジェクトグループは、この文脈において、１以上のオブジェクトのグループを記述するために用いられる。当該グループは、結合されて、より効率的で、そのグラフィックレンダリングシステムに特有のオブジェクト（のセット）を構成する。結合されたオブジェクトは、単一のオブジェクトのグループと比較して、より複雑であっても良いが、グラフィックレンダリングシステムは、オブジェクトグループをより効率的に扱うことができるであろう。もし、グラフィックレンダリングシステムにとって、それらが描かれていた元々のフォーマットよりもより好ましいフォーマットに変換されることが可能であれば、単一オブジェクトを一つのオブジェクトグループとして分類してもよい。
【０００６】
オブジェクトグループ検出スキーム（object group detection schemes）は、典型的に、オブジェクトをグループ化して、より効率的／望ましいオブジェクトのセットを構成することができるかどうかを決定するために利用される。システム設計者は、特に検出スキームを調整して、これらのオブジェクトの非効率性を検出し、修正する。”修正された”グラフィックオブジェクトデータは、オリジナルよりも、より複雑化しがちであるが、特定のグラフィックレンダリングシステムに対して最適化されており、そのようなレンダリングシステムを含むシステムをより効率的なものとするであろう。
【０００７】
各検出スキームは、グラフィックオブジェクトの異なるグループを検出し、結合して、複雑なグラフィックオブジェクトを形成する。検出スキームでは、しばしば１以上の同一オブジェクトが利用されるために、レンダリングシステムが複数の検出スキームを含んでいる場合には検出スキームにおける摩擦が生ずる可能性がある。
［発明の概要］
【０００８】
本発明の目的は、既存の装置における１以上の不利益を実質的に克服する、或いは、少なくとも改善することである。
【０００９】
本発明の第１の側面によれば、オブジェクトグループを、複数の受信したオブジェクトから形成するための方法が提供される。当該方法は、前記受信したオブジェクトを記述するデータを少なくとも一つの検出スキームへ送信する工程であって、各検出スキームは、優先度と関連づけられたオブジェクトグループタイプとを有し、前記受信したオブジェクトが前記関連づけられたオブジェクトグループタイプのオブジェクトグループの一部を形成するかどうかを検出するように動作する工程と、前記少なくとも一つの検出スキームから、前記受信したオブジェクトが前記オブジェクトグループの一部を形成するかどうかの通知を受信する工程と、１以上の前記オブジェクトグループが、完全に形成されたかどうかを決定する工程であって、少なくとも部分的に形成されたオブジェクトグループがリストを形成する工程と、完全に形成されたオブジェクトグループを前記優先度に基づいてレンダリングのために出力する工程とを、前記受信したオブジェクトのそれぞれについて備えることを特徴とする。
【００１０】
本発明の第２の側面によれば、複数の受信したオブジェクトからオブジェクトグループを構成するためのグラフィックレンダリングシステムが提供される。当該グラフィックレンダリングシステムは、複数の検出スキームであって、各検出スキームが優先度及び関連づけられたオブジェクトグループタイプを有し、前記関連づけられたオブジェクトグループタイプのオブジェクトグループの部分を形成するオブジェクトであるかを検出するように動作する複数の検出スキームと、受信したオブジェクトを記述するデータを少なくとも一つの検出スキームへ送信し、前記少なくとも一つの検出スキームから、前記受信されたオブジェクトが前記オブジェクトグループの一部を形成するかどうかの通知を受信し、少なくとも部分的に形成されたオブジェクトグループがリストを形成する場合に１以上の前記オブジェクトグループが完全に形成されたかどうかを決定し、前記優先度に基づいて完全に形成されたオブジェクトグループをレンダリングモジュールへ送信するためのマネージングモジュールとを備えることを特徴とする。
【００１１】
本発明の別の側面によれば、上述の方法を実行するためのコンピュータプログラムが記録されたコンピュータで読み取り可能な記録媒体を含むコンピュータプログラム製品が提供される。
【００１２】
本発明の１以上の実施形態は、添付する図面を参照して記述されるものである。
【００１３】
［最良の実施形態を含む詳細な記述］
処理ステップや特徴を説明するために添付図面の何れかを引用するところ、かかる図面において同一の参照番号が付された処理ステップ及び／又は特徴は、特に断りがない限りは、同一の機能や処理を表すものである。
【００１４】
図１は、多目的のコンピュータシステム１００を示しており、コンピュータシステム１００の１以上の出力装置に対してオブジェクトのレンダリングを行うために利用される。当該出力装置には、例えば、ディスプレイ１１４やプリンタ１１５がある。コンピュータシステム１００は、コンピュータモジュール１０１、キーボード１０２及びマウス１０３のような入力装置、プリンタ１１５及びディスプレイ１１４を含む出力装置から構成されるものである。
【００１５】
コンピュータモジュール１０１は、少なくとも一つのプロセッサユニット１０５、メモリーユニット１０６、ハードディスクドライブ１１０及びフロッピー（登録商標）ディスクドライブ１１１を典型的に含むところの記憶装置１０９、及び、多くの入出力（Ｉ／Ｏ）インタフェースを含むものである。入出力インタフェースは、ディスプレイ１１４と組み合わされるビデオインタフェース１０７、キーボード１０２及びマウス１０３用のＩ／Ｏインタフェース１１３、及び、プリンタ１１５用のインタフェース１０８を含む。コンピュータシステム１００内で実行されるオペレーティングシステムは、キーボード１０２及びマウス１０３からの入力を認識する、ディスプレイ１１４及びプリンタ１１５に出力を送信する、ファイルやディレクトリの記録を、記憶装置１０９に保存する、及び、ハードディスクドライブ１１０及びフロッピー（登録商標）ディスクドライブ１１１をを制御する、といった基本的なタスクを実行する。オペレーティングシステムはまた、アプリケーションプログラムを実行するためのソフトウェアプラットフォームを提供する。
【００１６】
図２は、出力装置１１４又は１１５の何れかにオブジェクトをレンダリングする処理に含まれる図１のコンピュータシステム１００のモジュールを示す図である。アプリケーションプログラム２１０はプロセッサ１０５内で実行され、例えばワードプロセッサのようなプログラムである。このプログラムにより、ページベースの文書データが生成され、各ページ内にはグラフィックオブジェクトが含まれる。グラフィックオブジェクトは典型的には、テキスト、ライン、フィルリージョン（fill regions）、画像データを含む。
【００１７】
文書が出力装置１１４や１１５上にレンダリングされる場合、アプリケーションプログラム２１０は、文書の各ページを連続するグラフィックコマンドとして、コンピュータシステム１００の元々のオペレーティングシステムにより提供されるグラフィックインタフェースサービス２２０へ送信する。グラフィックコマンドは、当該ページのグラフィックオブジェクトを記述する。グラフィックインタフェースサービス２２０のセットは、グラフィックデバイスインタフェース（ＧＤＩ）レイヤーとして既知であり、全てのアプリケーションプログラムにグラフィックス機能のリッチセットを提供する一般的なアプリケーションプログラミングインタフェースである。
【００１８】
ＧＤＩレイヤー２２０は、デバイスドライバ２３０が最も効率的に処理を行うであろうとＧＤＩレイヤー２２０が判断するフォーマットと、出力装置１１４又は１１５の解像度とにおいて、グラフィックオブジェクトをデバイスドライバ２３０へ提供する。実際、ＧＤＩレイヤー２２０は、アプリケーションプログラム２１０と出力装置１１４又は１１５との間を仲介するものであり、それによりデバイスドライバ２３０は、例えば、長方形ブロックの画像データを描画したり、シンプルな領域を単一色で塗りつぶしたりするといった、より小さな機能セット（a much smaller set of functionality）をサポートすることが可能となる。
【００１９】
デバイスドライバ２３０は、グラフィックレンダリングシステムとしても公知であるが、ＧＤＩレイヤー２２０から受け付けたグラフィックオブジェクトをレンダリングする。レンダリングは、ＧＤＩレイヤー２２０から受け付けたグラフィックオブジェクトをデバイスドライバ２３０により画素に変換する処理である。当該画素は出力装置１１４又は１１５へ送られる。アプリケーションプログラム２１０とグラフィックインタフェースサービス２２０はソフトウェアにより構成されるが、デバイスドライバ２３０はソフトウェア、ハードウエア又はそれらの組み合わせにおいて実現されても良い。
【００２０】
好適な実施形態において、グラフィックレンダリングシステム２３０によるレンダリング処理は、多目的コンピュータ１００のプロセッサ１０５により実行されるソフトウェアにおける命令により有効化される。当該ソフトウェアは、例えば、記憶手段１０９を含めた、コンピュータ可読媒体に格納されていてもよい。そのようなソフトウェアやコンピュータプログラムが格納されたコンピュータ可読媒体は、コンピュータプログラム製品である。
【００２１】
図３は、グラフィックレンダリングシステム３１０を示しており、そこには、４つの検出スキーム３１１から３１４が含まれている。検出スキーム３１１から３１４のそれぞれは、シンプルなグラフィックオブジェクトの異なるコンビネーションを結合して、それぞれに複雑なグラフィックオブジェクトを生成する。例えば、検出スキーム３１１は、水平線３２１と垂直線３２２とを結合して、十字３２３を形成している。
【００２２】
しかしながら、入力オブジェクト３３１が、グラフィックレンダリングシステム３１０により受け付けられた場合、オブジェクト３３１は、検出スキーム３１１から３１３までによりそれぞれ形成される複雑なグラフィックオブジェクトの一部を形成し得るシンプルなオブジェクトとして、検出スキーム３１１から３１３の３つにより検出されることになる。なお、このオブジェクト３３１は、垂直線である。検出スキーム３１１から３１３はシンプルなグラフィックオブジェクトを共有しているが、各手法３１１から３１３は、共通のオブジェクトを共有するかもしれない他の全ての検出スキーム３１１から３１４と通信して、当該オブジェクトの出力が１度だけ行われるようにしなければならない。そこで、各検出スキーム３１１から３１４は優先度を有している必要がある。ここで優先度とは、オブジェクトグループタイプについて与えられた順位付けである。特定の検出スキーム３１１から３１４に割り当てられる優先順位の番号が小さくなればなるほど、当該特定の検出スキームによって検出されるオブジェクトグループタイプに対する優先度が上がることとなる。検出スキーム３１１から３１４において最も高い優先度を有するものが、その検出スキームがオブジェクトグループタイプを形成するのに必要とするオブジェクトを全て入手することとなる。
【００２３】
優先度ベースではなく、検出スキームの完全なインタラクションとする場合、グラフィックレンダリングシステム３１０において、個々の検出スキーム３１１から３１４は、他のいずれかの検出スキーム３１１から３１４と同一のオブジェクトを利用することができないので、グラフィックレンダリングシステムにおいて最も効率的にグループ化されたグラフィックオブジェクトのセットを出力することはほとんど不可能となるであろう。
【００２４】
検出スキーム３１１から３１４が互いに通信しあうことを必要とする上述の要求は、新しい検出スキームが実行される際の容易性を損なうものである。より多くの検出スキームがグラフィックレンダリングシステムに追加されると、通信プロトコルは典型的に複雑化し、レンダリングシステム３１０内における実行速度が減少したり、符号の複雑さが増大したりといった逆の効果がもたらされることとなる。さらに、新しい検出スキームを導入するための適切なベースがない場合には、新たなオブジェクトグループ検出スキームを実施するための容易性が損なわれ、ソフトウェアの再利用性に影響が及ぶこととなる。
【００２５】
図４は、本発明に対応するグラフィックレンダリングシステム４００の好適な実施形態を示す図である。グラフィックレンダリングシステム４００は、レンダリングモジュール４０５、オブジェクトグループマネージングモジュール４１０及び複数の検出スキーム４２１から４２３を含み、これらの全てが好ましくは、プロセッサ１０５により実行される命令によって有効化される。
【００２６】
検出スキーム４２１から４２３の目的は、グラフィックオブジェクトをオブジェクトグループにグループ化することにより、図２のＧＤＩレイヤー２２０から受け付けたグラフィックオブジェクトの”デザイラビリティ（desirability）”を向上させることにある。これにより、レンダリングモジュール４０５に、グラフィックオブジェクトから画素への変換をより効率的に行わせることができる。異なるレンダリングモジュール４０５におけるデザイラビリティは、いくつかのレンダリングモジュール４０５がコンパクトなオブジェクトを選択するのに対し、他のレンダリングモジュール４０５が、より単純化されたオブジェクトのセットを選択する点で、異なるかもしれない。４２１から４２３の各検出スキームは、ある特定のオブジェクトグループを形成するために必要とされるグラフィックオブジェクトを"認識する（recognises）"。それゆえに、各検出スキーム４２１から４２３は、それぞれに特有のオブジェクトグループを形成するために必要とされる所定数のオブジェクトを格納する。
【００２７】
大抵の場合、検出スキーム４２１から４２３、特に検出スキーム４２２及び４２３は、同一のグラフィックオブジェクトを利用してそれぞれのオブジェクトグループを形成する。これらの２つのオブジェクトグループは、オーバラップしていると呼ばれる。オブジェクトグループマネージングモジュール４１０は、グラフィックレンダリングシステム４００により受信された各オブジェクトを、現在のオブジェクトタイプと関連する個々の検出スキームに送信し、検出されたオブジェクトグループの正否についての応答を格納する。各オブジェクトタイプは、０以上の検出スキームと所定の関連性を有する。オブジェクトグループマネージングモジュール４１０は、個々の検出スキーム４２１から４２３までからの結果を利用してマネージングを行い、グループ化されたオブジェクト又は単一オブジェクトを含んでもよい現在アクティブなオブジェクトグループ（これは、個々の検出スキームによって保持されている）の出力を制御する。
【００２８】
このようにするために、オブジェクトグループマネージングモジュール４１０は、オーバラップしているオブジェクトを有する検出スキーム４２１から４２３の間を仲介し、どのオブジェクトグループがどのオブジェクトに割り当てられるかを決定する。オブジェクトグループマネージングモジュール４１０は、検出スキーム４２１から４２３とレンダリングモジュール４０５との間でコミュニケータ及びオーガナイザとして効果的に振る舞い、個々の検出スキーム４２１から４２３が互いに通信し合う必要性を低減する。
【００２９】
オブジェクトグループマネージングモジュール４１０はまた、各検出スキーム４２１から４２３によって形成されるオブジェクトグループのいずれにも属しないオブジェクトの出力を扱い、また、オブジェクトグループには属しているかもしれないが、オブジェクトグループが完結しないようないかなるオブジェクトの出力も扱う。オブジェクトグループマネージングモジュール４１０は、この意味において、個々の検出スキーム４２１から４２３を制御し、組織化する（organize）マネージャとして動作し、グラフィックレンダリングシステム４００への及び、当該システム４００からのオブジェクトの流れをも制御する。
【００３０】
検出スキーム４２３が最も高い優先度を割当られており、それに続くのが４２１である。この例において、検出スキーム４２２及び４２３はオーバラップしているので、検出スキーム４２３はそのオブジェクトグループを、検出スキーム４２２に優先して形成することとなる。
【００３１】
以下のように、レンダリングモジュール４０５は、始動すると（upon initiation）、コンフィギュレーションデータをオブジェクトグループマネージングモジュール４１０へ送信する。コンフィギュレーションデータには、典型的には、グラフィックレンダリングシステム４００内に実装されている検出スキーム４２１から４２３の優先度、コールバック機能（callback functions）のリスト、及び、検出スキーム４２１から４２３のそれぞれに関するコンフィギュレーションデータのリストが含まれている。コンフィギュレーションデータは、オブジェクトグループが形成されるかどうかを検出スキーム４２１から４２３のそれぞれがどのように決定するかにつき、所定の制限を設定するために利用される。特に、"Always Formed（常に形成される）"とのフラグは、設定されるか又は設定されない。設定される場合、このフラグは、オブジェクトグループがいかなる数（１以上）のオブジェクトからでも完成されるオブジェクトグループであることを示す。そのようなオブジェクトグループはそれ故に、後述するように、例えより高い優先度のオブジェクトグループが共通する幾つかのオブジェクトを有していたとしても、出力の目的のために完成されたグループとして扱われる。コールバック機能は、検出スキーム４２１から４２３を読み出すために利用される。
【００３２】
２つのコールバック機能が、検出スキーム４２１から４２３のそれぞれと関連して存在する。即ち、認識コールバック機能（a recognize callback function）と、フラッシュコールバック機能（a flush callback function）である。認識コールバック機能に呼応して、検出スキーム４２１から４２３は、ステータスフラグを送り返すことにより、オブジェクトグループの検出ステータスをオブジェクトグループマネージングモジュール４１０に通知する。このステータスフラグは、以下のいずれかの意味を有することができる。
【００３３】
オブジェクトグループが完成したこと（現在のオブジェクトも含む）(object group complete (including the current object))
オブジェクトグループが完成し（現在のオブジェクトは含まず）、現在のオブジェクトが新しいグループに受け入れられたこと(object group complete (not including the current object) and current object has been accepted into a new group)
オブジェクトグループが完成し（現在のオブジェクトは含まず）、現在のオブジェクトが新しいグループに受け入れられていないこと(object group complete (not including the current object) and current object has not been accepted into a new group)
現在のオブジェクトにより新しいオブジェクトグループが開始され、完成したこと(new object group started and complete, by the current object)
オブジェクトグループが依然として形成中であること（”削除された”）(object group still forming ("detected"))
オブジェクトグループが失敗したこと（現在のオブジェクトを含む）(object group failed (including the current object))
オブジェクトグループが失敗し（現在のオブジェクトを含まず）、現在のオブジェクトが新しいオブジェクトグループに受け入れられていないこと(object group failed (not including the current object) and current object is not accepted into a new object group)
オブジェクトグループが失敗し（現在のオブジェクトを含まず）、現在のオブジェクトが新しいオブジェクトグループに受け入れられていること(object group failed (not including the current object) and current object is accepted in a new object group)
オブジェクトが受け入れられていないこと(object not accepted)
新しいオブジェクトグループが開始されたこと（”ポジティブ”ステータス）(new object group started ("positive" status))
フラッシュコールバック機能は、検出スキーム４２１から４２３に、完成したオブジェクトグループ若しくは単一オブジェクトを出力させる。
【００３４】
その動作において、レンダリングモジュール４０５は、グラフィックオブジェクト４３１から４３８をＧＤＩレイヤー２２０（図２）から一つずつ受信する。オブジェクト４３１から４３８は、レンダリングモジュール４０５によりオブジェクトグループマネージングモジュール４１０へ送信される。レンダリングモジュール４０５は特に、特定のオブジェクトが属するであろうオブジェクトグループタイプ、これらのオブジェクトタイプの数及びオブジェクト自体をオブジェクトグループマネージングモジュール４１０に提供する。オブジェクトは、所定の構造においてラッピングされ、当該構造のヘッダは、オブジェクトのオブジェクトグループタイプとそのようなタイプの数とを含む。オブジェクトはまた、レンダリングモジュール４０５によりメモリー１０６（図１）内にセーブされる。
【００３５】
図５Ａ、図５Ｂは、オブジェクトグループマネージングモジュール４１０によって実行されるプロセス５００のフロー図である。プロセス５００の処理工程は、メモリー１０６へロードされ、プロセッサ１０５によって実行されるたソフトウェアによって有効化される。オブジェクトグループマネージングモジュール４１０は、プロセス５００を開始し、ステップ５１０において、オブジェクトグループマネージングモジュール４１０はオブジェクト及び関連するデータをレンダリングモジュール４０５からを受け付け、それをオブジェクトリストに格納する。オブジェクトグループマネージングモジュール４１０はまた、オブジェクトに対するポインタをメモリー１０６へセーブする。
【００３６】
ステップ５１２では、オブジェクトグループマネージングモジュール４１０は、オブジェクトグループ認識フラグ（object group recognition flag）がセットされているかどうかを決定する。オブジェクトグループ認識フラグは、オブジェクトグループマネージングモジュール４１０のオン／オフステータスを制御する。もしオブジェクトグループ認識フラグがセットされていない場合、オブジェクトグループマネージングモジュール４１０はステップ５２０において、"検出されていない（not detected）"とのステータスメッセージをレンダリングモジュール４０５へ送信することにより、レンダリングモジュール４０５へコントロールを返す。レンダリングモジュール４０５は、通常の手法によりオブジェクトをレンダリングする。
【００３７】
また、もしオブジェクトグループマネージングモジュール４１０が、オブジェクトグループ認識フラグがセットされていると決定した場合には、オブジェクトグループマネージングモジュール４１０はステップ５１４において、受け付けたオブジェクトに関連する検出スキーム４２１から４２３のそれぞれの認識機能（a recognise function）を呼び出す。もし現在トラックされているオブジェクトグループが存在する場合、即ち、検出スキームが、アクティブオブジェクトグループリストにおいてアクティブなステータスを有する場合、アクティブな検出スキームの認識機能もまた呼び出される。アクティブオブジェクトグループリストは、オブジェクトグループマネージングモジュール４１０が現在トラッキングしている現在アクティブなオブジェクトグループのリストである。当該リストにおける各アイテムには、オブジェクトグループのタイプ、オブジェクトグループの優先度、オブジェクトグループがアクティブであるオブジェクト、及び、オブジェクトグループのステータスが含まれる。ステータスは"アクティブ"、"完成(complete)"、又は"失敗(failed)"のいずれかであっても良く、リスト中のいかなるアイテムも、"失敗"フラグが立っている場合には、直ちに削除される。
【００３８】
各検出スキーム４２１から４２３は、受け付けたグラフィックオブジェクトが、それ以前に受け付けたオブジェクトとグループ化される可能性のあるオブジェクトの一つであるかどうかを、もしそれがある場合により複雑なグラフィックオブジェクトを形成するために決定し、その結果として、オブジェクトグループマネージングモジュール４１０へ応答を送信する。オブジェクトグループマネージングモジュール４１０は、このようにしてステップ５１６において、検出スキーム４２１から４２３より検出ステータスを受信する。
【００３９】
ステップ５１８において、オブジェクトグループマネージングモジュール４１０は、現在トラッキングされているオブジェクトグループが存在するかどうかを、アクティブオブジェクトグループリストにおいて"アクティブ"なステータスを有するオブジェクトグループが現在存在するかどうか、或いは、検出スキーム４２１から４２３のいずれかが肯定的な検出ステータスをステップ５１６において返してきたかどうか、により決定する。もし現在トラッキングされているオブジェクトが存在しない場合、プロセス５００はステップ５２０へ移行して、"検出されていない（not detected）"とのステータスメッセージがレンダリングモジュール４０５へ送信される。このようにして、単一グラフィックオブジェクトがいかなるオブジェクトグループタイプにも属しないことが決定され、メモリースペースの浪費を防止するために当該オブジェクトが通常の手法によりレンダリングモジュール４０５によってレンダリングされても良い。
【００４０】
もし、ステップ５１８においてオブジェクトグループマネージングモジュール４１０が、少なくとも一つのオブジェクトグループがアクティブオブジェクトグループリストにおいて現在"アクティブ"なステータスにあるかどうか、又は、検出スキーム４２１から４２３の少なくとも一つが肯定的な検出ステータスを返してきたかどうか、を決定した場合、オブジェクトグループマネージングモジュール４１０は、ステップ５２２においてアクティブオブジェクトグループリストを更新する。このことは、各検出スキーム４２１から４２３が"肯定的な（positive）"検出ステータスを返した各オブジェクトグループに関して"アクティブ"なステータスを有するエントリーを生成すること、各検出スキーム４２１から４２３が"検出した（detected）"との検出ステータスを返した現在のオブジェクトを含むように、既存のエントリーのオブジェクトリストを修正すること、及び、各検出スキームが、オブジェクトグループが失敗（object group failed）との検出ステータスのいずれかを返した、正しく形成することに失敗した全てのオブジェクトグループを削除すること、を含むものである。検出スキームは、それがトラッキングするようにデザインされているオブジェクトグループにフィットしないオブジェクトを受け付けた場合に、オブジェクトグループが失敗（object group failed）とのステータスフラグのうちの１つを戻すであろう。ステップ５２２では、対応する検出スキーム４２１から４２３が"完成"の検出ステータスのいずれかのフォームを返すところの、アクティブオブジェクトグループリストにおける各オブジェクトグループに関してステータスを"完成（complete）"に設定することが含まれる。
【００４１】
プロセス５００はステップ５２４に移行し、オブジェクトグループマネージングモジュール４１０は、このステージにおいて出力されるべきオブジェクトグループ又は独立のオブジェクトが存在するかどうかを決定する。オブジェクトグループ又は単一オブジェクトは、もしアクティブオブジェクトグループリストにおいて最も高い優先度のオブジェクトグループが"完成"のステータスを有する場合に出力される。
【００４２】
もし、オブジェクトグループマネージングモジュール４１０が、オブジェクトグループ又は単一オブジェクトが出力されるべきであると決定した場合、プロセス５００はステップ５２６へ移行する。そうでない場合は、プロセス５００はステップ５３６に移行する。
【００４３】
ステップ５２６では、オブジェクトグループマネージングモジュール４１０が、"完成"のステータスを有するアクティブオブジェクトグループリストにおける優先度が最も高いオブジェクトグループのデータを、アクティブオブジェクトグループリストから出力リストへ転送する。ここで、出力リストとは、出力されるべきオブジェクトグループ及び単一オブジェクトのリストである。出力リストには、出力されるオブジェクトグループのタイプ、出力されるオブジェクトの範囲、及び、オブジェクトグループ又は単一オブジェクトのいずれを出力するかが含まれている。
【００４４】
ステップ５２８では、オブジェクトグループマネージングモジュール４１０が、オブジェクトグループまたはオブジェクトがリストから削除されたことを受けて、アクティブオブジェクトグループリストを更新する。ここでは、ステップ５２６で転送されたオブジェクトグループにオーバラップするオブジェクトグループを見つける（locate）ために、アクティブなオブジェクトグループにおけるエントリを優先度の降順にトラバース（traversing）することを含む。そのようなオブジェクトグループのそれぞれに対応する検出スキームの"常に形成(Always Formed)"のフラグがチェックされる。もし、このフラグが設定されている場合、出力リストに既に登録されているどのオブジェクトに対するポインタも、当該エントリのオブジェクトリストから削除される。もし、フラグがセットされていない場合は、当該オブジェクトグループはアクティブなオブジェクトグループから削除される。
【００４５】
プロセス５００は、ステップ５２８からステップ５２９へ移行して、オブジェクトグループマネージングモジュール４１０が、アクティブなオブジェクトグループ中に出力リストに転送されるべき更なるオブジェクトグループ又は単一オブジェクトが存在するかどうかを決定する。一旦オブジェクトグループマネージングモジュール４１０が、オブジェクトグループ又は単一オブジェクトが出力されるべきであると決定すると、現在オブジェクトグループマネージングモジュール４１０がトラッキングしている全てのオブジェクトは、出力される必要が出てくるであろう。但し、新しいオブジェクトグループに受け入れられ、他のグループには受け入れられていないことを条件として現在のオブジェクトは除外される。このことは、オブジェクトの順番は、レンダリング時に維持されることを保証するものである。もしオブジェクトグループマネージングモジュール４１０がステップ５２９において、より多くのオブジェクトが出力リストに転送される必要があると決定した場合、プロセス５００はステップ５２６へ戻る。そうでなければ、ステップ５３２へ移行する。
【００４６】
このように、オブジェクトグループマネージングモジュール４１０が、アクティブなオブジェクトグループから出力リストへ転送すべきオブジェクトグループ及び単一オブジェクトが存在しないと決定した場合、ステップ５３２において、オブジェクトグループマネージングモジュール４１０は、出力リストに応じてレンダリングモジュール４０５における適当なレンダリング機能を（検出スキームの一部として提供されるフラッシュコールバック機能を介して）呼び出す。オブジェクトがグラフィックレンダリングシステム４００へ入力された順番を維持するために、出力リストはリストの最後のオブジェクト／オブジェクトグループから最初へとたどられる。レンダリング機能を呼び出すことにより、対応するオブジェクト又はオブジェクトグループが出力装置１１４又は１１５へレンダリングされる。出力リストが一度完全に処理されると、オブジェクトグループマネージングモジュール４１０はステップ５３４においてオブジェクトリストをクリアする。
【００４７】
オブジェクトグループマネージングモジュール４１０は、次にステップ５３６において受け付けたオブジェクトが処理されたことをレンダリングモジュール４０５に通知する。例え出力リストが空であるためにレンダリングされるオブジェクトが存在しない場合であっても、この通知は送信され、最新に受け付けられたグラフィックオブジェクトがオブジェクトグループに包含されたか、部分的にオブジェクトグループを形成しているかを意味することとなる。プロセス５００は、次のオブジェクトの受信に応じて再度実行される。
【００４８】
グラフィックレンダリングシステム４００、特にオブジェクトグループマネージングモジュール４１０の処理を、図６Ａから図６Ｇを参照して以下により詳細に説明する。例えば、グラフィックレンダリングシステム４００はテキストオブジェクトをＧＤＩレイヤー２２０から受信し、テキストオブジェクトをレンダリングし、ディスプレイ１１４へ画素を出力する。
【００４９】
例に示すグラフィックレンダリングシステム４００は、２つの検出スキームを含む。第１の検出スキームは、オブジェクトグループ"Ｔｈｅ"を構成するテキストオブジェクトを検出し、"ＴＨＥ"との語を形成する画素を出力する。第２の検出スキームは、オブジェクトグループ"Ｔｈｅｓｅ"を構成するテキストオブジェクトを検出し、"ＴＨＥＳＥ"との語を形成する画素を出力する。この例において、オブジェクトグループ"Ｔｈｅｓｅ"はより高い優先度を与えられている。更に、検出スキームには"常に形成(Always Formed)"のフラグがセットされていない。レンダリングシステム４００のレンダリングモジュール４０５によって受信されたテキストオブジェクトは、"Ｔｈｅｓｅ "との語を形成しており、ここでは、文字"ｅ"の後にスペースが続いている。テキストオブジェクトは、１つずつオブジェクトグループマネージングモジュール４１０へ送信され、各オブジェクトはそのオブジェクトグループタイプにより組合わされる。
【００５０】
ここで図６Ａを参照すると、オブジェクトグループマネージングモジュール４１０の第１の状態６０１が示されている。オブジェクトグループマネージングモジュール４１０は、まずオブジェクト"Ｔ"をレンダリングモジュール４０５から受け付け、当該オブジェクトをオブジェクトリストに格納する。よって、オブジェクトリストには、この時点で"Ｔ"が含まれている。オブジェクトグループマネージングモジュール４１０は、受信したオブジェクト"Ｔ"に関連するそれぞれの検出スキームの認識機能を呼び出す。
【００５１】
各検出スキームは、受信したグラフィックオブジェクトが、より複雑なグラフィックオブジェクトを形成するためにグループ化される可能性のあるオブジェクトの一部であるかどうかを決定し、その結果に応じた検出ステータスをオブジェクトグループマネージングモジュール４１０へ送信する。図６Ａは、２つの検出スキームについての状態６０２及び６０３を示している。各検出スキームは、オブジェクト"Ｔ"を認識し、"new object group started（新しいオブジェクトグループの開始）"のステータスをオブジェクトグループマネージングモジュール４１０へ戻す。これは、オブジェクトグループマネージングモジュール４１０に、当該検出スキームに送信されたオブジェクトが、将来的にオブジェクトグループの一部として受け入れられる可能性があることを伝えるものである。
【００５２】
"new object group started"のステータスを受信した後、オブジェクトグループマネージングモジュール４１０は、２つの検出スキームが肯定的な検出ステータスを返したと決定することにより、現在トラッキングされている２つのアクティブなオブジェクトグループが存在することを決定する。オブジェクトグループマネージングモジュール４１０は、検出スキームから受信した情報を、"アクティブ"なステータスを有する２つの新しいエントリ（それぞれは各検出スキームに関連づけられている）を生成することにより、（現在は空である）アクティブオブジェクトグループリストに追加する。オブジェクトグループマネージングモジュール４１０の状態６０１はまた、更新されたアクティブオブジェクトグループリストを示している。
【００５３】
アクティブオブジェクトグループリストにおいて現在最も優先度が高いオブジェクトグループ、この例ではオブジェクトグループタイプ"ＴＨＥＳＥ"は、"完成（complete）"のステータスを有していないので、このステージにおいてはオブジェクトの出力はなされない。
【００５４】
オブジェクトグループマネージングモジュール４１０は次に、受信したオブジェクトが処理され、この時点においてレンダリングのためにオブジェクトが出力される必要がないことをレンダリングモジュール４０５へ通知する。
【００５５】
図６Ｂは、その後の状態を示しており、ここではオブジェクトグループマネージングモジュール４１０がオブジェクト"ｈ"を、第２のオブジェクトとしてレンダリングモジュール４０５から受け付け、状態６１１に示されるように当該オブジェクトをオブジェクトグループマネージングモジュール４１０のオブジェクトリストに格納している状態を示している。オブジェクトグループマネージングモジュール４１０は、各検出スキームの認識機能を呼び出す。これは、両方の検出スキームがオブジェクト"ｈ"に関連しているためだけではなく、両方の検出スキームのオブジェクトグループタイプがアクティブオブジェクトグループリストにリストされているからでもある。各検出スキームは、各オブジェクトにつき一度は呼び戻されることになる点は注意すべきである。
【００５６】
検出スキームの状態６１２及び６１３において示されるように、各検出スキームは、受信したグラフィックオブジェクト"ｈ"が、オブジェクト"Ｔ"とグループ化されてより複雑なグラフィックオブジェクトを形成する可能性があるオブジェクトの一つであるかどうかを決定する。この結果に従って、各検出スキームは"検出（detected）"との検出ステータスをオブジェクトグループマネージングモジュール４１０へ送信する。ここで、もし、検出スキームがオブジェクト"Ｔ"を従前のオブジェクトとして検出していない場合には、"検出"の検出ステータスを戻すことはない。検出スキームは、隣接するオブジェクトを順序に従わずに扱うこともできるが、その場合であってもモジュールはいかなる異なる機能も必要としない。
【００５７】
オブジェクトグループマネージングモジュール４１０は、検出スキームから受信した情報によりアクティブオブジェクトグループリストのエントリを更新する。オブジェクトグループマネージングモジュール４１０の状態６１１は、両方のオブジェクトグループタイプが、"アクティブ"なステータスを有し、オブジェクト１及び２、即ち"Ｔ"及び"ｈ"とそれぞれが関連していることを示している。
【００５８】
アクティブオブジェクトグループリストにおいて最も優先度の高いオブジェクトグループが、"完成（complete）"のステータスを依然として有していない場合、このステージにおいてオブジェクトは出力されない。オブジェクトグループマネージングモジュール４１０は、レンダリングモジュール４０５へ、受信したオブジェクトが処理されたことを通知する。
【００５９】
オブジェクトグループマネージングモジュール４１０は次に、レンダリングモジュール４０５からオブジェクト"ｅ"を受け付け、オブジェクトリスト内に当該オブジェクトを格納する。さらに、受信したオブジェクト"ｅ"と関連する検出スキーム及びアクティブオブジェクトグループリストにおけるオブジェクトグループタイプと関連する全ての検出スキーム、本例においては両方の検出スキーム、の認識機能を呼び出す。
【００６０】
両方の検出スキームは、オブジェクト"ｅ"が各オブジェクトグループを形成するためのグループ化される可能性のあるオブジェクトの一つであると決定する。さらに、オブジェクトグループ"Ｔｈｅ"を構成するテキストオブジェクトを検出する検出スキームは、そのオブジェクトグループを形成するために必要とされる全てのオブジェクトが受信されたと決定し、オブジェクトグループマネージングモジュール４１０に"完成（complete）"のステータスを戻す。図６Ｃは、検出スキームの状態６２２及び６２３を示す。
【００６１】
オブジェクトグループマネージングモジュール４１０は、検出スキームから受信した情報を、既存の２つのエントリを更新することにより、アクティブオブジェクトグループリストに追加する。オブジェクトグループマネージングモジュール４１０の状態６２１は、オブジェクトグループタイプ"ＴＨＥ"が現在"完成（complete）"状態にあることを示している。
【００６２】
アクティブオブジェクトグループリストにおいて最も優先度の高いオブジェクトグループが依然として"完成（complete）"のステータスを有していないので、このステージにおいてもオブジェクトは出力されない。オブジェクトグループマネージングモジュール４１０は、レンダリングモジュール４０５へ、受信したオブジェクトが処理されたことを通知する。
【００６３】
図６Ｄを参照すると、オブジェクトグループマネージングモジュール４１０はオブジェクト"ｓ"をレンダリングモジュール４０５から次に受け付け、当該オブジェクトをオブジェクトリストに格納する。オブジェクトグループマネージングモジュール４１０は、オブジェクトグループタイプ"ＴＨＥＳＥ"に関連する検出スキームのみの認識機能を呼び出す。これは、オブジェクトグループタイプ"ＴＨＥ"に関連する検出スキームが受信したオブジェクト"ｓ"に関連しないだけでなく、アクティブオブジェクトグループリスト内にアクティブなオブジェクトグループタイプに関連する検出スキームが存在しないからでもある。オブジェクトタイプ"ＴＨＥ"は"完成（complete）"ステータスを有している。
【００６４】
オブジェクトグループタイプ"ＴＨＥＳＥ"に関連する検出スキームは、オブジェクト"ｓ"がオブジェクトグループを形成するためにグループ化される可能性のあるオブジェクトの一つであると決定し、"検出（detected）"の検出ステータスをオブジェクトグループマネージングモジュール４１０へ再度返す。図６Ｄはまた、検出スキームの状態６３２及び６３３を示している。オブジェクトグループマネージングモジュール４１０は、オブジェクトグループタイプ"ＴＨＥＳＥ"のエントリを更新することにより、アクティブオブジェクトグループリストへ受信した情報を追加する。オブジェクトグループマネージングモジュール４１０の状態６３１は、オブジェクトグループタイプ"ＴＨＥＳＥ"が、依然として"アクティブ"なステータスを有しており、オブジェクト１から４と関連していることを示している。完成したオブジェクトグループタイプ"ＴＨＥ"のエントリは不変のままである。
【００６５】
アクティブオブジェクトグループリストにおいて最も優先度が高いオブジェクトグループが依然として"完成（complete）"の状態を有していないので、このステージでもオブジェクトは出力されない。オブジェクトグループマネージングモジュール４１０は、レンダリングモジュール４０５へ受信したオブジェクトが処理されたことを通知する。
【００６６】
本例は図６Ｅに継続し、オブジェクトグループマネージングモジュール４１０は、レンダリングモジュール４０５からオブジェクト"ｅ"を受け付け、当該オブジェクトをオブジェクトリスト内にオブジェクト５として格納する。オブジェクトグループマネージングモジュール４１０は、オブジェクト"ｅ"が両方のオブジェクトグループタイプに関連するので、両方の検出スキームの認識機能を呼び出す。
【００６７】
オブジェクトグループタイプ"ＴＨＥＳＥ"に関連する検出スキームは、オブジェクト"ｅ"が、それ以前に受信したオブジェクトとグループ化されてオブジェクトグループを形成する可能性があるオブジェクトの一つであると決定し、オブジェクトグループマネージングモジュール４１０へ"完成（complete）"の検出ステータスを返す。
【００６８】
オブジェクトグループタイプ"ＴＨＥ"に関連する検出スキームは、先行するオブジェクトがオブジェクト"ｈ"でないために、オブジェクト"ｅ"をそれ以前に受信したオブジェクトとグループ化される可能性のあるオブジェクトの一つとは認識せず、"受け付けず（not accepted）"の検出ステータスをオブジェクトグループマネージングモジュール４１０へ返す。図６Ｅはまた、検出スキームの状態６４２及び６４３を示している。
【００６９】
オブジェクトグループマネージングモジュール４１０は、オブジェクトグループタイプ"ＴＨＥＳＥ"のエントリを更新することにより、アクティブオブジェクトグループリストに受信した情報を追加する。オブジェクトグループマネージングモジュール４１０の状態６４１は、オブジェクトグループタイプ"ＴＨＥＳＥ"が、現時点で"完成（complete）"のステータスを有し、オブジェクト１から５と関連づけられていることを示している。完成したオブジェクトグループタイプ”ＴＨＥ”のエントリは不変のままである。
【００７０】
オブジェクトグループマネージングモジュール４１０は、アクティブオブジェクトグループリストにおいて、"完成（complete）"のステータスを有する最も優先度の高いオブジェクトグループタイプと、このステージにおいて出力されるべきオブジェクトグループ又は単一オブジェクトとを決定する。そのために、また、図６Ｆに示されるように、オブジェクトグループマネージングモジュール４１０はオブジェクトグループタイプ"ＴＨＥＳＥ"のデータをアクティブオブジェクトグループリストから出力リストへ転送する。オブジェクトグループマネージングモジュール４１０はまた、アクティブオブジェクトグループリストを更新してオブジェクトグループタイプ"ＴＨＥＳＥ"がリストから削除された事実を反映するとともに、オブジェクトグループタイプ"ＴＨＥ"が、出力リストに移されたオブジェクトグループタイプ"ＴＨＥＳＥ"とオーバラップしており、ゆえに"failed"ステータスを取得しているので、これをアクティブオブジェクトグループリストから削除する。
【００７１】
オブジェクトグループマネージングモジュール４１０は、次にアクティブオブジェクトグループリストが空になり、出力されるべきオブジェクトグループ又は単一オブジェクトが最早存在しないと決定する。オブジェクトグループマネージングモジュール４１０は、出力リストに従ってレンダリングモジュール４０５内の適切なレンダリング機能を呼び出す。出力リストにはただ１つのオブジェクトグループが存在している。オブジェクトグループタイプ"ＴＨＥＳＥ"のレンダリング機能を呼び出すことにより、"ＴＨＥＳＥ"の語を形成する画素が出力装置１１４又は１１５へレンダリングされる。オブジェクトグループマネージングモジュール４１０は、その時点でトラッキングしているオブジェクトを有しておらず、よって、アクティブオブジェクトグループリストにはオブジェクトグループタイプが存在しないが、レンダリングモジュール４０５へ受信したオブジェクトを処理したことを通知する。
【００７２】
最後に、オブジェクトグループマネージングモジュール４１０は" "（空白(space character)）のオブジェクトをレンダリングモジュール４０５から受け付け、図６Ｇの状態６６１に示されるオブジェクトリストに当該オブジェクトを格納する。当該オブジェクト" "は、どの検出スキームとも関連していないので、検出スキームは呼び出されない。
【００７３】
次に、アクティブオブジェクトグループリストは空であるので、オブジェクトグループマネージングモジュール４１０は"検出されず（not detected）"とのステータスのメッセージをレンダリングモジュール４０５へ送信する。レンダリングモジュール４０５は、単一オブジェクトグループタイプのオブジェクト" "を、通常の手法においてレンダリングする。これにより図６Ａから図６Ｇまでに示す例が完結する。
【００７４】
ステップ５２６（図５Ｂ）における、オブジェクトグループマネージングモジュール４１０による、アクティブオブジェクトグループリストから出力リストへのデータ転送について、以下に他の例を用いてより詳細に説明する。図７Ａは、１４個のオブジェクトと、それらと関連づけられたアクティブなオブジェクトグループタイプを示している。４つのオブジェクトグループタイプを含むアクティブオブジェクトグループリストが示され、それらは"完成（complete）"のステータスを有している。ここで、オブジェクトグループタイプ１と関連づけられた検出スキームは、"常に形成（Always Formed）"のフラグセットを有している点に注意すべきである。アクティブオブジェクトグループリストを生成したステップのシーケンスを経ない場合、各オブジェクトグループタイプは完成となるので、より高い優先度を有する他のアクティブなオブジェクトグループタイプが、オブジェクト又はオブジェクトグループが出力されるのを妨げる。
【００７５】
しかしながら、この例における現在のステージでは、アクティブオブジェクトグループリストにおいて最も優先度の高いオブジェクトグループタイプであるオブジェクトグループタイプ４が"完成（complete）"のステータスを有する。よって、オブジェクト９から１４にかかるオブジェクトグループタイプ４のデータは、図示されるように出力リストへ転送される。
【００７６】
もし、同一の優先度を有する１以上の完成したオブジェクトグループが存在する（このことはオブジェクトグループタイプが同一であることを意味するであろう）場合、より後にオブジェクトグループ化された（the later object grouping）オブジェクトグループが、まず出力リストへ転送されるであろう。
【００７７】
ステップ５２８において、オブジェクトグループマネージングモジュール４１０は、オブジェクトグループタイプ４とオーバラップするオブジェクトグループについて、アクティブなリストをスキャンする。図７Ｂに示すように、オブジェクトグループタイプ３はオブジェクトグループタイプ４とオーバラップしており、"Always Formed"のフラグがセットされていないので、オブジェクトグループタイプ３はアクティブオブジェクトグループリストから削除される。
【００７８】
オブジェクトグループタイプ３を削除した後、オブジェクトグループマネージングモジュール４１０は、次に優先度が高い完成したオブジェクトグループをアクティブオブジェクトグループリスト内において探索する。これにより、優先度８を有するオブジェクトグループタイプ２が探索される。このオブジェクトグループが出力リストに追加される前に、オブジェクトグループマネージングモジュール４１０は、このオブジェクトグループと出力リストに追加されたばかりのオブジェクトグループとの間にオブジェクトのギャップが存在しないことチェックして確認する。
【００７９】
図７Ｃに示す場合はオブジェクト８のように、もしギャップが存在する場合には、当該単一オブジェクトは、次のオブジェクトグループが転送される前に、出力リストへ移される。隣接して存在する複数の単一オブジェクトについては、一つのエントリが出力リストに挿入されるだけでよい。このエントリは特に出力されるべきオブジェクトの番号のリストを含むであろう。
【００８０】
図７Ｄは、アクティブオブジェクトグループリスト内で最も高い優先度を有する完成されたオブジェクトグループ（この場合は、オブジェクトグループタイプ２である）のデータが出力リストへ転送される場合を示している。オブジェクト４から７をカバーするオブジェクトグループタイプ２が出力リストへ一旦転送されると、アクティブオブジェクトグループリストが未完成のオブジェクトグループのために再度スキャンされる。図７Ｅを参照すると、オブジェクトタイプ１に関連する検出スキームは"常に形成（Always Formed）"のフラグセットを有するので、オブジェクト４はオブジェクトグループ１のオブジェクトリストから削除される。そして、オブジェクト１から３をカバーするオブジェクトグループタイプ１が、出力リストへ転送される。
【００８１】
全てのオブジェクトが一度出力リストへ移動されると、オブジェクトグループマネージングモジュール４１０は、フラッシュ機能の呼び出しを開始し、オブジェクトグループと単一オブジェクトの出力を行う。出力リストと連携して、オブジェクトグループマネージングモジュール４１０はリストの最後のアイテムから最初のアイテムへ向かって動作する。これは、リストの最後のアイテムがオブジェクトグループマネージングモジュール４１０を通過する最初のオブジェクトであったためであり、それ故に出力リストは出力タスクのスタックとなる。出力リストの後ろから処理するので、オブジェクトグループマネージングモジュール４１０は、オブジェクトグループタイプ１からスタートし、オブジェクトグループタイプ２、単一オブジェクト８、最後にオブジェクトグループタイプ４の順となる。以上により、図７Ａから図７Ｅまでに示す例が完結する。
【００８２】
上述のように、グラフィックレンダリングシステム４００は、既存の検出スキームとは独立に、グラフィックレンダリングシステム４００内における通信の複雑性を増加させることなく、新しい検出スキームを導入できるという利点を有することが理解される。特に、オブジェクトグループマネージングモジュール４１０は、グラフィックオブジェクト、検出スキーム及びそれらの優先度のマネージメントを通じたスキーム間の複雑な通信の必要性を排除して、優先度ベースのオブジェクトグループ検出スキームを効果的に実施するための基礎を提供するものである。
【産業上の利用可能性】
【００８３】
上述した構成は、コンピュータグラフィックス及び印刷業界に適用可能なものであることは明らかである。
【００８４】
上述の内容は本発明のいくつかの実施形態に過ぎず、それらに対する修正及び／若しくは変更は本発明の範囲及び精神から逸脱することなく行うことが可能であり、実施形態は単に例示的なものであって、限定的な意味を有するものではない。
【図面の簡単な説明】
【００８５】
【図１】多目的のコンピュータシステムの構成の一例を示す図である。
【図２】コンピュータシステムの出力装置にオブジェクトをレンダリングする際に利用されるコンピュータシステムのモジュールの一例を示す図である。
【図３】複数の検出スキームを含むグラフィックレンダリングシステムの一例を示す図である。
【図４】本発明に対応するグラフィックレンダリングシステムの好適な実施形態を示す図である。
【図５Ａ】オブジェクトグループマネジングモジュールにより実行される処理のフローチャートである。
【図５Ｂ】オブジェクトグループマネジングモジュールにより実行される処理のフローチャートである。
【図６Ａ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図６Ｂ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図６Ｃ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図６Ｄ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図６Ｅ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図６Ｆ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図６Ｇ】グラフィックレンダリングシステムの処理の一例を示す図である。
【図７Ａ】アクティブなオブジェクトグループリストから出力リストへのデータの転送の一例を示す図である。
【図７Ｂ】アクティブなオブジェクトグループリストから出力リストへのデータの転送の一例を示す図である。
【図７Ｃ】アクティブなオブジェクトグループリストから出力リストへのデータの転送の一例を示す図である。
【図７Ｄ】アクティブなオブジェクトグループリストから出力リストへのデータの転送の一例を示す図である。
【図７Ｅ】アクティブなオブジェクトグループリストから出力リストへのデータの転送の一例を示す図である。
【図１】
2004295900.tif 000003
【図２】
2004295900.tif 000004
【図３】
2004295900.tif 000005
【図４】
2004295900.tif 000006
【図５Ａ】
2004295900.tif 000007
【図５Ｂ】
2004295900.tif 000008
【図６Ａ】
2004295900.tif 000009
【図６Ｂ】
2004295900.tif 000010
【図６Ｃ】
2004295900.tif 000011
【図６Ｄ】
2004295900.tif 000012
【図６Ｅ】
2004295900.tif 000013
【図６Ｆ】
2004295900.tif 000014
【図６Ｇ】
2004295900.tif 000015
【図７Ａ】
2004295900.tif 000016
【図７Ｂ】
2004295900.tif 000017
【図７Ｃ】
2004295900.tif 000018
【図７Ｄ】
2004295900.tif 000019
【図７Ｅ】
2004295900.tif 000020
【外国語明細書】
1. Title of Invention
GRAPHICAL OBJECT GROUP MANAGEMENT SYSTEM
2. Field of the Invention
The present invention relates generally to the management of objects in an object rendering system and, in particular, to the management of graphical object detection schemes within the object rendering system.
3. Background
Rendering is the process by which graphics objects are converted to pixels.  Graphics rendering systems typically use a painters algorithm style of rendering where each object is drawn onto a frame buffer as it arrives.  Other graphics rendering systems use a 2-stage approach, where the graphics rendering system firstly converts all incoming objects into some intermediate format for the page, and the second stage renders a scanline at a time.
No matter the type of graphics rendering system, efficiency problems are suffered due to the nature of some of the graphic commands received from application programs.  For example, a common drawing application program passes a gradient fill to the graphics rendering system as a group of adjacent overlapping rectangles, each with a slightly different flat colour, to give the impression of a smooth gradient fill.  Although true to the nature of the original object, the graphic objects are abundant with redundant data. 
In an attempt to reduce the above inefficiencies, it has been proposed to detect simple graphic objects that may be combined into more complex graphic objects, and combining such graphic objects into object groups, thereby removing redundant data and reducing the number of raster operations.  An object group, in this context, is used to describe a group of one or more objects that may be combined to form a more efficient (set of) object(s) specific to the graphics rendering system.  The combined object(s) may be more complex than the group of single objects, but the graphics rendering system may be able to handle the object group(s) more efficiently.  Single objects may be classified as an object group if they can be transformed into a format more desirable to the graphics rendering system than the format in which they were originally represented.
Object group detection schemes are typically used for determining whether or not the objects can be grouped to form a more efficient/desirable set of objects.  System designers specifically tailor detection schemes to detect and "correct" these object inefficiencies.  The "corrected" graphic object data, although most likely more complex than the original, would be optimised for the specific graphics rendering system, causing the system which includes such a rendering system to be more efficient.
Each detection scheme detects and combines a different grouping of graphic objects to form a complex graphic object.  Due to the fact that detection schemes often use one or more of the same objects, conflict amongst detection schemes would occur when the rendering system includes multiple detection schemes.
4. Summary
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.  
According to a first aspect of the present invention there is provided a method of forming object groups from a plurality of received objects, said method comprising for each received object the steps of:
passing data describing said received object to at least one detection scheme, each detection scheme having a priority and an associated object group type, and operative to detect whether said received object forms part of an object group of said associated object group type;
receiving notification from said at least one detection scheme of whether said received object forms part of said object group(s);
determining whether one or more of said object groups are completely formed, where at least partly formed object groups form a list; and
outputting for rendering a completely formed object group based on said priorities.
According to a second aspect of the present invention there is provided a graphics rendering system for forming object groups from a plurality of received objects, said graphics rendering system comprising:
a plurality of detection schemes, each detection scheme having a priority and an associated object group type, and operative to detect whether an object forms part of an object group of said associated object group type;
a managing module for passing data describing a received object to at least one detection scheme, for receiving notification from said at least one detection scheme of whether said received object forms part of said object group(s), for determining whether one or more of said object groups are completely formed, where at least partly formed object groups form a list, and for passing a completely formed object group to a rendering module based on said priorities.
According to another aspect of the present invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for implementing the methods described above.
Other aspects of the invention are also disclosed.
5. Detailed Description including Best Mode
Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.
Fig. 1 illustrates a general-purpose computer system 100 that may be used for rendering objects to one or more output devices of the computer system 100, such as a display device 114 or a printing device 115.  The computer system 100 is formed from a computer module 101, input devices such as a keyboard 102 and mouse 103, and output devices including the printer 115 and the display device 114.
The computer module 101 includes at least one processor unit 105, a memory unit 106, a storage device 109 which typically includes a hard disk drive 110 and a floppy disk drive 111, and a number of input/output (I/O) interfaces.  The input/output (I/O) interfaces include a video interface 107 that couples to the video display 114, an I/O interface 113 for the keyboard 102 and mouse 103, and an interface 108 for the printer 115.  The components 105 to 113 of the computer module 101 communicate via an interconnected bus 104.  An operating system executing within the computer system 100 performs basic tasks, such as recognizing input from the keyboard 102 and mouse 103, sending output to the display screen 114 and printer 115, keeping track of files and directories on the storage device 109, and controlling the hard disk drive 110 and the floppy disk drive 111.  The operating system also provides a software platform on top of which application programs can execute. 
Fig. 2 illustrates modules of the computer system 100 (Fig. 1) involved in a process of rendering objects to one of the output devices 114 or 115.  An application program 210 executing within the processor 105, such as a word processor, creates page-based document data, where each page contains graphic objects.  The graphic objects typically include text, lines, fill regions and image data.
When a document is to be rendered on the output device 114 or 115, the application program 210 passes each page of the document as a series of graphic commands to graphics interface services 220 provided by the native operating system of the computer system 100.  The graphic commands describe the graphic objects of the page.  The set of graphics interface services 220 is known as the graphics device interface (GDI) layer, and is generally an application programming interface providing a rich set of graphics functionality to all application programs.
The GDI layer 220 provides graphic objects to a device driver 230 in a format that the GDI layer 220 judges the device driver 230 would process most efficiently, and at a resolution of the output device 114 or 115.  In fact, the GDI layer 220 mediates between the application program 210 and the output device 114 or 115, thereby enabling the device driver 230 to support a much smaller set of functionality, such as drawing rectangular blocks of image data, and filling simple regions with flat color.
The device driver 230, also known as a graphics rendering system, renders the graphics objects received from the GDI layer 220.  Rendering is the process by which the graphics objects received from the GDI layer 220 are converted to pixels by the device driver 230.  The pixels are sent to the output device 114 or 115.  Whilst the application program 210 and the graphics interface services 220 are formed by software, the device driver 230 may be performed in software, hardware or a combination thereof.
In the preferred implementation, the process of rendering by the graphics rendering system 230 is effected by instructions in software that are carried out by the processor 105 of a general-purpose computer 100.  The software may be stored in a computer readable medium, including the storage device 109, for example.  A computer readable medium having such software or computer program recorded on it is a computer program product.  
Fig. 3 shows a graphics rendering system 310 that includes four detection schemes 311 to 314.  Each of the detection schemes 311 to 314 combines a different combination of simple graphic objects to form their respective complex graphic object.  For example, detection scheme 311 combines a horizontal line 321 and a vertical line 322 to form a cross 323.
However, when input object 331 is received by the graphics rendering system 310, three of the detection schemes 311 to 313 detect object 331, which is a vertical line, as a simple object that may be used to form the respective complex graphic objects formed by those detection schemes 311 to 313.  Since the detection schemes 311 to 313 share simple graphic objects, each scheme 311 to 313 has to communicate with every other scheme 311 to 314 that may share a common object to ensure that the object is only output once.  Each detection scheme 311 to 314 needs to have a priority.  Priority is the ranking given to an object group type.  The lower the priority number assigned to a particular detection scheme 311 to 314, and hence the object group type detected by the particular detection scheme, the higher the priority.  The detection scheme 311 to 314 having the highest priority gets all the objects it requires to form its object group type. 
Without a priority base and complete detection scheme interaction it would almost be impossible to output the most efficient set of grouped graphic objects within a graphics rendering system 310, as individual detection schemes 311 to 314 could not use the same objects as any other detection scheme 311 to 314 within the graphics rendering system 310.
The above requirement that detection schemes 311 to 314 need to communicate with one another greatly reduces the ease at which new detection schemes may be implemented.  As more detection schemes are added to the graphics rendering system 310, the communication protocols typically grow in complexity, which has the adverse effect of reducing execution speed and increasing code complexity within the graphics rendering system 310.  Furthermore, without a proper base to introduce new detection schemes, the ease of implementing a new object group detection scheme is reduced, and software reusability suffers.
Fig. 4 illustrates a preferred implementation of a graphics rendering system 400 according to the present disclosure.  The graphics rendering system 400 includes a rendering module 405, an object group managing module 410 and a number of detection schemes 421 to 423, all of which are preferably effected by instructions executed by the processor 105.
The purpose of the detection schemes 421 to 423 is to increase the "desirability" of the graphic objects received from the GDI layer 220 (Fig. 2) by grouping graphic objects into object groups, thereby allowing the rendering module 405 to more efficiently convert the graphic objects to pixels.  Desirability amongst different rendering modules 405 may differ in that some rendering modules 405 prefer objects that are compact, while other rendering modules 405 prefer a set of more simplistic objects.  Each detection scheme 421 to 423 "recognises" those graphic objects needed to form one particular object group.  Therefore, each detection scheme 421 to 423 stores a certain number of objects needed to form its particular object group.
As is often the case, detection schemes 421 to 423, and in particular detection schemes 422 and 423, use the same graphic object(s) to form their respective object groups.  These two object groups are said to be overlapping.  The object group managing module 410 passes each object received by the graphics rendering system 400 to individual detection schemes that are associated with the current object type and stores the response about the success/failure of a detected object group.  Each object type has a predefined association to 0 or more detection schemes.  The object group managing module 410 uses the results from the individual detection schemes 421 to 423 to manage, and control the output of, currently active object groups (held by the individual detection schemes), which may include grouped objects and single objects.
In order to do so, the object group managing module 410 mediates between the detection schemes 421 to 423 that have overlapping objects to decide which object group is assigned which objects.  The object group managing module 410 effectively acts as a communicator and organiser between the detection schemes 421 to 423 and the rendering module 405, reducing the need for the separate detection schemes 421 to 423 to communicate with one another.
The object group managing module 410 also handles the outputting of objects that do not belong to any of the object groups formed by the respective detection schemes 421 to 423 and also handles the outputting any objects that may have belonged to an object group but the object group failed to complete.  The object group managing module 410 in this sense acts as a manager to control and organise individual detection schemes 421 to 423, as well as controlling the flow of objects into and out of the graphics rendering system 400.
It is noted that detection scheme 423 has been assigned the highest priority, followed by detection scheme 421.  In this example, because detection schemes 422 and 423 are overlapping, detection scheme 423 forms its object group in preference to detection scheme 422. 
In the following, the rendering module 405, upon initialisation, sends configuration data to the object group managing module 410.  The configuration data typically includes the priorities of the detection schemes 421 to 423 implemented in the graphics rendering system 400, a list of callback functions, and a list of configuration data for each of the specific detection schemes 421 to 423.  Configuration data is used to set specific limits on how each detection scheme 421 to 423 decides whether an object group is formed.  In particular, an 'Always Formed' flag is either set or not set.  When set, this flag indicates that an object group can be completed by any number (greater than equal to one) of objects.  Such an object group can therefore be treated as a completed group for output purposes even if a higher priority object group has some objects in common with it, as will be explained later. The callback functions are used to call the detection schemes 421 to 423.
There are two callback functions associated with each detection scheme 421 to 423 namely a recognise callback function and a flush callback function.  In response to a recognise callback function the detection scheme 421 to 423 reports on the detection status of an object group to the object group managing module 410 by sending back a status flag which may have one of the following meanings:
object group complete (including the current object);
object group complete (not including the current object) and current object has been accepted into a new group;
object group complete (not including the current object) and current object has not been accepted into a new group;
new object group started and complete, by the current object;
object group still forming ("detected");
object group failed (including the current object);
object group failed (not including the current object) and current object is not accepted into a new object group;
object group failed (not including the current object) and current object is accepted in a new object group;
object not accepted; and
new object group started ("positive" status).
The flush callback function causes the detection scheme 421 to 423 to output a complete object group or a single object.
In operation, the rendering module 405 receives graphic objects 431 to 438 from the GDI layer 220 (Fig. 2), one by one.  The objects 431 to 438 are passed by the rendering module 405 to the object group managing module 410.  In particular, the rendering module 405 provides the object group managing module 410 with object group types that the particular object may belong to, the number of these object types and the object itself.  The object is wrapped in a structure such that the header of the structure contains the object group types of the object and the number of such types.  The object is also saved by the rendering module 405 in memory 106 (Fig. 1).
Fig. 5 is a flow diagram of a process 500 performed by the object group managing module 410.  The steps of the process 500 are effected by software loaded into memory 106 and executed by the processor 105.  The object group managing module 410 starts process 500 in step 510 where the object group managing module 410 accepts the object and associated data from the rendering module 405 and stores it in an object list.  The object group managing module 410 also saves a pointer to the object in memory 106.  
Step 512 follows where the object group managing module 410 determines whether an object group recognition flag is set.  The object group recognition flag controls the on/off status of the object group managing module 410.  If the object group recognition flag is not set, then the object group managing module 410 returns in step 520 control to the rendering module 405 by passing a "not detected" status message to the rendering module 405.  The rendering module 405 then renders the object in the normal manner.
Alternatively, if the object group managing module 410 determines that the object group recognition flag is set, then the object group managing module 410 calls in step 514 a recognise function of each of the detection schemes 421 to 423 associated with the received object.  If there are any object groups currently being tracked, i.e. the detection scheme has an active status in an active object group list, then the recognise function of those active detection schemes is also called.  The active object group list is a list of the currently active object groups that the object group managing module 410 is currently tracking.  Each item in the list includes the type of the object group, the priority of the object group, the objects over which the object group is active, and the status of the object group.  The status may be "active", "complete", or "failed", although any item in the list with a "failed" flag is immediately removed.
Each detection scheme 421 to 423 determines whether the received graphic object is one of the objects that may be grouped with previously received objects, if any, to form a more complex graphic object and sends a response to the object group managing module 410 accordingly.  The object group managing module 410 thus receives in step 516 a detection status from the detection schemes 421 to 423. 
In step 518 the object group managing module 410 determines whether there are any object groups currently being tracked by determining whether there are currently object groups with "active" status in the active object group list or whether any of the detection schemes 421 to 423 returned a positive detection status in step 516.  If no objects are currently being tracked, then process 500 proceeds to step 520 where a "not detected" status message is sent to the rendering module 405.  It has thus been determined that the single graphics object does not belong to any object group type, and the object may be rendered in the usual manner by the rendering module 405 to avoid the object wasting memory space.  
If the object group managing module 410 determines in step 518 that there is currently at least one object group with "active" status in the active object group list, or that at least one of the detection schemes 421 to 423 returned a positive detection status, then the object group managing module 410 updates the active object group list in step 522.  This includes creating an entry with "active" status for each object group where the respective detection scheme 421 to 423 returned a "positive" detection status, amending the object lists of existing entries to include the current object where the respective detection scheme 421 to 423 returned a 'detected' detection status, and removing any object groups that fail to correctly form where the respective detection scheme returned any one of the object group failed detection statuses.  A detection scheme will return one of the object group failed status flags when it receives an object that does not fit into the object group that it is designed to track.  Step 522 also includes setting the status to 'complete' for each object group in the active object group list, where the corresponding detection scheme 421 to 423 returned any form of 'complete' detection status.
Process 500 then continues to step 524 where the object group managing module 410 determines whether any object groups or separate objects are to be output at this stage.  Object groups or single objects are output if the highest priority object group in the active object group list has a status of "complete".
If the object group managing module 410 determines that an object group or single object(s) is to be output, then process 500 continues to step 526.  Alternatively process 500 continues to step 536.
In step 526 the object group managing module 410 transfers the data of the highest priority object group in the active object group list that has a status of "complete" from the active object group list to an output list.  An output list is a list of object groups and single objects that are to be output.  The output list includes the type of object group to output, the range of objects to output, and whether to output an object group or single objects.
Step 528 follows where the object group managing module 410 updates the active object group list to reflect the fact that an object group or object has been removed from the list.  This involves traversing the entries in the active object group list in descending priority order to locate object groups that had overlaps into the object group that was transferred in step 526.  The 'Always Formed' flag of the corresponding detection scheme to each such object group is checked.  If it is set, pointers to any objects that have already been placed in the output list are removed from the object list of that entry.  If the flag is not set, any  that object group is removed from the active object group list.
From step 528 the process 500 the continues to step 529 where the object group managing module 410 determines whether there are any further object groups or single objects in the active object group list that need to be transferred to the output list.  It should be noted that once the object group managing module 410 determines that an object group or single object is to be output, then all the objects that it is currently tracking will need to be output, except the current object, on condition that it has been accepted into a new object group and not into any other object group.  This ensures that the order of objects is preserved when rendering.  If the object group managing module 410 determines in step 529 that more objects need to be transferred to the output list, then process 500 returns to step 526.  Alternatively process 500 continues to step 532.
Thus, in the event that the object group managing module 410 determines that there are no more object groups and single object(s) to be transferred from the active object group list to the output list, then in step 532 the object group managing module 410 calls the appropriate rendering functions (via the flush callback function provided as part of a detection scheme) in the rendering module 405 according to the output list.  To preserve the order in which objects came into the graphics rendering system 400, the output list is worked from the last object/object group in the list to the first.  By calling the rendering functions the corresponding objects or object groups are rendered to the output device 114 or 115.  Once the output list has been processed completely, the object group managing module 410 clears the object list in step 534.
The object group managing module 410 next in step 536 notifies the rendering module 405 that the received object has been processed.  Even if there were no objects rendered because the output list was empty, this notification is sent meaning that the latest received graphics object was incorporated into an object group or partly formed object group.  The process 500 is again performed upon receipt of a next object.
The operation of the graphics rendering system 400, and in particular the object group managing module 410, will now be illustrated by way of an example with reference to Figs. 6A to 6G.  In the example, the graphics rendering system 400 receives text objects from the GDI layer 220, renders the text objects, and outputs pixels to the display 114.
The graphics rendering system 400 of the example includes 2 detection schemes (not illustrated).  The first detection scheme detects the text objects making up the object group "The" and outputs pixels to form the word "THE".  The second detection scheme detects the text objects making up the object group "These", and outputs pixels to form the word "THESE".  In the example the object group "These" is given the higher priority.  Furthermore, neither detection scheme has its 'Always Formed' flag set.  The text objects received by the rendering module 405 of the graphics rendering system 400 forms the word "These ", having a space character following the second "e" character.  The text objects are passed one by one to the object group managing module 410, each object being accompanied by its object group types.
Referring now to Fig. 6A where a first state 601 of the object group managing module 410 is illustrated.  The object group managing module 410 first accepts the object "T" from the rendering module 405 and stores that object in an object list, which now contains one object "T".  The object group managing module 410 calls the recognise function of each of the detection schemes associated with the received object "T".
Each detection scheme then determines whether the received graphic object is one of the objects that may be grouped to form its more complex graphic object and sends a detection status to the object group managing module 410 accordingly.  Fig. 6A illustrates the states 602 and 603 of the 2 respective detection schemes.  Each of the detection schemes recognised the object "T" and returned a "new object group started" status to the object group managing module 410.  This tells the object group managing module 410 that the object passed to the detection schemes may be accepted as part of an object group in the future.  
After receiving the "new object group started" status, the object group managing module 410 determines that there are now two active object groups currently being tracked by determining that two detection schemes returned a positive detection status.  The object group managing module 410 adds the information received from the detection schemes to the (currently empty) active object group list by creating 2 new entries with "active" status, one associated with each detection scheme.  The state 601 of the object group managing module 401 also shows the updated active object group list.
As the highest priority object group currently in the active object group list, which is the object group type "THESE" in the example, does not have a status of "complete", no objects are to be output at this stage.
The object group managing module 410 next notifies the rendering module 405 that the received object has been processed and that the object does not need to be output for rendering at this point in time.
Fig. 6B illustrates a following state where the object group managing module 410 accepts the object "h" as a second object from the rendering module 405 and stores that object in the object list shown in the state 611 of the object group managing module 410.  The object group managing module 410 then calls the recognise function of each of the detection schemes.  This is not only because both detection schemes are associated with the object "h", but also because the object group types of both the detection schemes are in the active object group list.  Note that each detection scheme is called back at most once per object.
As is illustrated in detection scheme states 612 and 613, each detection scheme determines that the received graphic object "h" is one of the objects that may be grouped with the object "T" to form its more complex graphic object.  Accordingly, each detection scheme sends a "detected" detection status to the object group managing module 410.  It is noted that the detection schemes would not have returned the "detected" detection status if they had not detected the object "T" as the previous object.  A detection scheme could be adapted to handle out of order contiguous objects, but the module need not function any differently.
The object group managing module 410 updates the entries in the active object group list with the information received from the detection schemes.  The state 611 of the object group managing module 401 shows that both object group types have an "active" status, and are associated with objects 1 and 2, which are "T" and "h" respectively.
It is still the case that the highest priority object group in the active object group list does not have a status of "complete", and no objects are to be output at this stage.  The object group managing module 410 notifies the rendering module 405 that the received object has been processed.
The object group managing module 410 next accepts the object "e" from the rendering module 405, stores that object in the object list, and calls the recognise function of each of the detection schemes associated with the received object "e" and all the detection schemes associated with the object group types in the active graphic object list, which are both detection schemes in the example.
Both detection schemes determine that the object "e" is one of the objects that may be grouped to form their respective object groups.  However, the detection scheme detecting the text objects making up the object group "The" determines that all the objects needed to form its object group have been received, and returns a status of "complete" to the object group managing module 410.  Fig. 6C illustrates the states 622 and 623 of the detection schemes. 
The object group managing module 410 adds the information received from the detection schemes to the active object group list by updating the existing 2 entries.  The state 621 of the object group managing module 401 shows that object group type "THE" now has a "complete" status.
It is still the case that the highest priority object group in the active object group list does not have a status of "complete", and no objects are to be output at this stage.  The object group managing module 410 notifies the rendering module 405 that the received object has been processed.
Referring now to Fig. 6D, the object group managing module 410 next accepts the object "s" from the rendering module 405, and stores that object in the object list.  The object group managing module 410 then calls the recognise function of the detection scheme associated with object group type "THESE" only.  This is because the detection scheme associated with object group type "THE" is not associated with the received object "s", and also because that detection scheme is not associated with an active object group type in the active graphic object list.  The object group type "THE" has a "complete" status.
The detection scheme associated with object group type "THESE" determines that the object "s" is one of the objects that may be grouped to form its object group and again returns a "detected" detection status to the object group managing module 410.  Fig. 6D also illustrates the states 632 and 633 of the detection schemes.  The object group managing module 410 adds the information received to the active object group list by updating the entry of object group type "THESE".  The state 631 of the object group managing module 410 shows that object group type "THESE" still has an "active" status and is associated with objects 1 to 4.  The entry of the completed object group type "THE" remains unchanged.
It is still the case that the highest priority object group in the active object group list does not have a status of "complete", and no objects are to be output at this stage.  The object group managing module 410 notifies the rendering module 405 that the received object has been processed.
The example follows in Fig. 6E where the object group managing module 410 accepts the object "e" from the rendering module 405, and stores that object in the object list as object 5.  The object group managing module 410 then calls the recognise function of both the detection schemes because the object "e" is associated with both object group types.
The detection scheme associated with object group type "THESE" determines that the object "e" is one of the objects that may be grouped with the previously received objects to form its object group and returns a "complete" detection status to the object group managing module 410.
The detection scheme associated with object group type "THE" does not recognise the object "e" as one of the objects that may be grouped with the previously received objects because the preceding object was not the object "h", and returns a "not accepted" detection status to the object group managing module 410.  Fig. 6E also illustrates the states 642 and 643 of the detection schemes.
The object group managing module 410 adds the information received to the active object group list by updating the entry of object group type "THESE".  The state 641 of the object group managing module 401 shows that object group type "THESE" now has a "complete" status and is associated with objects 1 to 5.  The entry of the completed object group type "THE" remains unchanged.
The object group managing module 410 now determines that the highest priority object group type in the active object group list has a status of "complete" and that object groups or separate objects are to be output at this stage.  In order to do so, and as is illustrated in Fig. 6F, the object group managing module 410 transfers the data of the object group type "THESE" from the active object group list to the output list.  The object group managing module 410 also updates the active object group list to reflect the fact that the object group type "THESE" has been removed from the list, and removes the object group type "THE" from the active object group list because it overlapped with the object group type "THESE" that was placed into the output list, and therefore acquired "failed" status.
The object group managing module 410 next determines that the active object group list is now empty, and that there are no more object groups or single objects to be output.  The example follows where the object group managing module 410 calls the appropriate rendering functions in the rendering module 405 according to the output list.  There is only one object group in the output list.  By calling the rendering function of the object group type "THESE", pixels to form the word "THESE" are rendered to the output device 114 or 115.  The object group managing module 410, which now has no objects that it is tracking, and accordingly no object group types in its active object group list, notifies the rendering module 405 that the received object has been processed.
Finally the object group managing module 410 accepts the object " " (space character) from the rendering module 405, and stores that object in the object list shown in state 661 of Fig. 6G.  Because the object " " is not associated with any of the detection schemes, no detection scheme is called.
Next, because the active object group list is empty, the object group managing module 410 sends a "not detected" status message to the rendering module 405.  The rendering module 405 then renders the single object group type object " " in the normal manner.  This concludes the example illustrated through Figs. 6A to 6G.
The transfer of data by the object group managing module 410 from the active object group list to the output list occurring in step 526 (Fig. 5) will now be described in more detail by means of another example.  Fig. 7A graphically illustrates 14 objects and the active object group types associated with them.  Also shown is the active object group list including 4 object group types, all of which having a status of complete.  Note also that the detection scheme associated with object group type 1 has its 'Always Formed' flag set.  Without going through the sequence of steps that created the active object group list, it is noted that as each respective object group type became complete, that there was another active object group type having a higher priority preventing objects and object groups to be output.
However, at the current stage of the example, object group type 4 having the highest priority of the object group types in the active object group list has a "complete" status.  Hence, the data of object group type 4, which spans objects 9 to 14, is transferred to the output list which is also shown.
If there is more than one complete object group with the same priority (which will mean that the object group types are the same), then the object group that is based on the later object grouping will be transferred to the output list first.
In step 528 the object group managing module 410 then scans the active list for object groups that had overlaps into object group type 4.  As is illustrated in Fig. 7B, because object group type 3 overlapped object group type 4, and its 'Always Formed' flag was not set, object group 3 is discarded from the active object group list.  
After discarding object group type 3 the object group managing module 410 then searches for the next highest completed object group within the active object group list.  This happens to be object group type 2, with a priority of 8.  Before this object group is put into the output list the object group managing module 410 checks to ensure there are no object gaps between this object group and the object group that was just placed into the output list.
In the case where there is a gap, as is the case with object 8 as is illustrated in Fig. 7C, then that single object is placed into the output list before the next object group is transferred.  For multiple single objects that are contiguous there only needs to be one entry inserted into the output list.  This entry will contain the list of object numbers to be output singularly.
Fig. 7D shows the case where the data of the completed object group with the highest priority in the active object group list is transferred to the output list, which is object group type 2.  Once object group type 2 covering objects 4 to 7 has been transferred to the output list, the active object group list is again scanned for non complete object groups.  Referring to Fig. 7E, because the detection scheme associated with object group type 1 has its 'Always Formed' flag set, object 4 is removed from object group 1's object list.  Object group type 1 covering objects 1 to 3 is then transferred to the output list.
Once all the objects have been moved into the output list, the object group managing module 410 starts to call the flush functions to output the object groups and single objects.  When working with the output list the object group managing module 410 works from the last item in the list to the first item.  This is because the last item in the list would have been the first objects to pass through the object group managing module 410 and hence the output list is a stack of output tasks.  Working from the back of the output list the object group managing module 410 starts from object group type 1, followed by object group type 2, single object 8, and finally object group type 4.  This concludes the example of Figs. 7A to 7E.
From the above it can be seen that the graphics rendering system 400 has the advantage that new detection schemes may be introduced independent of existing detection schemes and without a growth in complexity in the communication within the graphics rendering system 400.  In particular, the object group managing module 410 provides a basis for efficient implementation of priority based object group detection schemes without the need for complex inter-scheme communication through the management of graphic objects, detection schemes and their priorities.
6. Industrial Applicability
It is apparent from the above that the arrangements described are applicable to the computer graphics and printing industries.
The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive. 
7. Brief Description of the Drawings
One or more embodiments of the present invention will now be described with reference to the drawings, in which:
Fig. 1 illustrates a general-purpose computer system;
Fig. 2 illustrates modules of the computer system involved in rendering objects to output devices of the computer system;
Fig. 3 shows a graphics rendering system that includes multiple detection schemes;
Fig. 4 illustrates a preferred implementation of a graphics rendering system according to the present disclosure;
Fig. 5 is a flow diagram of a process performed by the object group managing module;
Figs. 6A to 6G illustrate the operation of the graphics rendering system by way of an example; and
Figs. 7A to 7E illustrate the transfer of data from an active object group list to an output list by way of an example.
1.  A method of forming object groups from a plurality of received objects, said method comprising for each received object the steps of:
passing data describing said received object to at least one detection scheme, each detection scheme having a priority and an associated object group type, and operative to detect whether said received object forms part of an object group of said associated object group type;
receiving notification from said at least one detection scheme of whether said received object forms part of said object group(s);
determining whether one or more of said object groups are completely formed, where at least partly formed object groups form a list; and
outputting for rendering a completely formed object group based on said priorities.
2.  The method as claimed in claim 1, wherein said outputting step outputs said completely formed object group if said completely formed object group is the object group in said list of a type associated with the detection scheme with a highest priority.
3.  The method as claimed in claim 1, wherein said object is passed to detection schemes having associated object group types where said received object is a potential member of an object group of said associated object group types, and detection schemes having object groups in said list.
4.  The method as claimed in claim 1 comprising the further step of outputting for rendering received objects not forming part of said object groups.
5.  The method as claimed in claim 1 comprising the further step of outputting for rendering previously received objects that were forming part of one or more object groups that have not been output, where at least one of the objects of said completely formed object groups has been output.
6.  The method as claimed in claim 5, wherein said previously received objects are output for rendering (i) individually or (ii) as a group, depending on an attribute of the detection scheme associated with the type of the object group of which said previously received objects form part.
7.  A graphics rendering system for forming object groups from a plurality of received objects, said graphics rendering system comprising:
a plurality of detection schemes, each detection scheme having a priority and an associated object group type, and operative to detect whether an object forms part of an object group of said associated object group type;
a managing module for passing data describing a received object to at least one detection scheme, for receiving notification from said at least one detection scheme of whether said received object forms part of said object group(s), for determining whether one or more of said object groups are completely formed, where at least partly formed object groups form a list, and for passing a completely formed object group to a rendering module based on said priorities.
8.  The graphics rendering system as claimed in claim 7, wherein said managing module passes said completely formed object group to said rendering module if said completely formed object group is the object group in said list of a type associated with the detection scheme with a highest priority.
9.  The graphics rendering system as claimed in claim 7, wherein said object is passed to detection schemes having associated object group types where said received object is a potential member of an object group of said associated object group types, and detection schemes having associated object groups in said list.
10.  The graphics rendering system as claimed in claim 7 wherein said managing module further passes received objects not forming part of said object groups to said rendering module.
11.  The graphics rendering system as claimed in claim 7 wherein said managing module further passes previously received objects to said rendering module, wherein said previously received objects were forming part of one or more object groups that have not been rendered, and at least one of the objects of said completely formed object groups has been rendered.
12.  The graphics rendering system as claimed in claim 11, wherein said previously received objects are passed to said rendering module (i) individually or (ii) as a group, depending on an attribute of the detection scheme associated with the type of the object group of which said previously received objects form part.
13.  A computer program product including a computer readable medium having recorded thereon a computer program for forming object groups from a plurality of received objects, said computer program for each received object comprising:
code for passing data describing said received object to at least one detection scheme, each detection scheme having a priority and an associated object group type, and operative to detect whether said received object forms part an object group of said associated object group type;
code for receiving notification from said at least one detection scheme of whether said received object forms part of said object group(s);
code for determining whether one or more of said associated object groups are completely formed where at least partly formed object groups form a list; and
code for outputting for rendering a completely formed object group based on said priorities.
14.  The computer program product as claimed in claim 13, wherein said code for outputting outputs said completely formed object group if said completely formed object group is the object group in said list of a type associated with the detection scheme with a highest priority.
1. ABSTRACT
A graphics rendering system (400) and method (500) are disclosed for forming object groups from input objects (431 through 438).  The graphics rendering system (400) comprises an number of detection schemes (421 to 423), a managing module (410) and a rendering module (405).  Each detection scheme (421 to 423) has a priority and an associated object group type, and is operative to detect whether an object forms part of an object group of the associated object group type.  The managing module (410) passes data describing a received input object to at least one of the detection schemes (421 to 423), and receives notification from the detection scheme(s) whether the object forms part of the object group(s).  The managing module (410) then determines whether one or more of the object groups are completely formed, where at least partly formed object groups form a list.  A completely formed object group is passed by the managing module (410) to the rendering module (405) for rendering based on the priorities of the detection schemes associated with the object group types of the object groups in the set.  The above avoids the need for complex inter-detection scheme communication through the management of graphic objects, detection schemes and their priorities.
2. Representative Drawing
なし
2004295900.tif 000021
2004295900.tif 000022
2004295900.tif 000023
2004295900.tif 000024
2004295900.tif 000025
2004295900.tif 000026
2004295900.tif 000027
2004295900.tif 000028
2004295900.tif 000029
2004295900.tif 000030
2004295900.tif 000031
2004295900.tif 000032
2004295900.tif 000033
2004295900.tif 000034
2004295900.tif 000035
2004295900.tif 000036
2004295900.tif 000037
2004295900.tif 000038