(57)【要約】      （修正有）【課題】グラフィカルオブジェクトをレンダリングする効率の良い方法を提供する。【解決手段】複数のオブジェクトを組み合わせる方法により行い、１組の連続するグラフィカルオブジェクトを効率よく組み合わせて、連続するグラフィカルオブジェクトの組み合わせを表現するハイレベルコンパイルドオブジェクトを生成し、コンパイルドオブジェクトをディスプレイリストへ出力する。コンパイルドオブジェクトは、関連するメタ塗りつぶしを備え、メタ塗りつぶしは、複合塗りつぶしであり、コンパイルドオブジェクトと関連する塗りつぶしの集合体を記述するために使用される。【選択図】図８Ｂ
2005267639.tif 000002
【特許請求の範囲】
【請求項１】
各々が所定のオブジェクトアウトラインと、所定のZ-オーダーと、関連する塗りつぶしを含み、特定のオブジェクトに関する当該オブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングする方法であって、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしを含み、前記複合塗りつぶしが、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含む、グループ化オブジェクトを形成する工程と、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングする工程と、
を備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とする方法。
【請求項２】
前記グループ化オブジェクトアウトラインは、前記所定のオブジェクトアウトライン又はその複数の部分のうちの１つ以上に従うことを特徴とする請求項１に記載の方法。
【請求項３】
前記オブジェクトは、Z-オーダーにおいて連続し、前記グループ化オブジェクトは、前記オブジェクトの中で最低のZ-オーダーを割り当てられることを特徴とする請求項１に記載の方法。
【請求項４】
前記オブジェクトが所定の基準を満たすか否かを判定する工程を更に備えることを特徴とする請求項１に記載の方法。
【請求項５】
同一の単色塗りつぶしを有する１つ以上のグラフィカルオブジェクトは、前記複合塗りつぶしにおいて、１つ以上の単色塗りつぶしとして表現されることを特徴とする請求項１に記載の方法。
【請求項６】
線形色変化を有する１つ以上のグラフィカルオブジェクトは、前記複合塗りつぶしにおいて、１つ以上の線形混合塗りつぶしとして表現されることを特徴とする請求項１に記載の方法。
【請求項７】
前記所定の基準のうちの１つは、前記オブジェクトの各々が２つの平行な辺を有することを特徴とする請求項４に記載の方法。
【請求項８】
前記所定の基準のうちの１つは、前記平行な辺の各々が同一の方向角を有することを特徴とする請求項７に記載の方法。
【請求項９】
前記所定の基準のうちの１つは、前記オブジェクトの各々が重複するか、または前記平行な辺の全長に沿って境を接することを特徴とする請求項８に記載の方法。
【請求項１０】
前記複合塗りつぶしにおける画素ランの長さを格納する工程を更に備えることを特徴とする請求項１に記載の方法。
【請求項１１】
前記塗りつぶしは、前記複合塗りつぶしにおいて、前記塗りつぶしを記述する塗りつぶしデータ構造の連係リストとして表現されることを特徴とする請求項１に記載の方法。
【請求項１２】
前記データ構造における第１の塗りつぶしを指示するポインタを格納する工程を更に備えることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記塗りつぶしの各々は、フラット塗りつぶしであることを特徴とする請求項１に記載の方法。
【請求項１４】
前記グラフィカルオブジェクトの各々のオブジェクトアウトラインは、１つ以上の稜線を含むことを特徴とする請求項１に記載の方法。
【請求項１５】
オブジェクトアウトラインはパスであることを特徴とする請求項１に記載の方法。
【請求項１６】
オブジェクトアウトラインは、複数の点により定義される多角形であることを特徴とする請求項１に記載の方法。
【請求項１７】
グラフィカルオブジェクトが、所定のオブジェクトアウトラインと、前記複合塗りつぶしと含み、当該所定のオブジェクトアウトラインは、前記グラフィカルオブジェクトが塗りつぶされるエリアを定義する、当該グラフィカルオブジェクトをレンダリングするための複合塗りつぶし方法であって、
前記複合塗りつぶしは、レンダリング時に前記グラフィカルオブジェクトが塗りつぶされるべき形式を定義する複数の塗りつぶしを含むデータ構造として構成されることを特徴とする複合塗りつぶし方法。
【請求項１８】
前記グラフィカルオブジェクトは、複数のグラフィカルオブジェクトから形成されることを特徴とする請求項１７に記載の複合塗りつぶし方法。
【請求項１９】
前記データ構造は、連係リストであることを特徴とする請求項１７に記載の複合塗りつぶし方法。
【請求項２０】
前記複合塗りつぶしにおけるトラッキングポイントを格納する工程を更に備えることを特徴とする請求項１記載の方法。
【請求項２１】
前記トラッキングポイントは、前記グループ化オブジェクトをレンダリングするために、前記複合塗りつぶし中における現在の塗りつぶしを判定するために使用されることを特徴とする請求項２０に記載の方法。
【請求項２２】
各々が所定のオブジェクトアウトラインと、所定のZ-オーダーと、関連する塗りつぶしと含み、特定のオブジェクトのオブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングする装置であって、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしを含み、前記複合塗りつぶしは、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含む、グループ化オブジェクトを形成するための組み合わせ手段と、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングするレンダリング手段と、
を備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とする装置。
【請求項２３】
各々が所定のオブジェクトアウトラインと、所定のZ-オーダーと、関連する塗りつぶしを含み、特定のオブジェクトに関する当該オブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングするためのコンピュータプログラムであって、当該プログラムが、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしと含み、前記複合塗りつぶしは、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含むグループ化オブジェクトを形成するためのコードと、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングするためのコードと、
備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とするコンピュータプログラム。
【請求項２４】
各々が所定のオブジェクトアウトラインと、所定のZ-オーダーと、関連する塗りつぶしを含み、特定のオブジェクトのオブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングするためのコンピュータプログラムを記録したコンピュータで読み取り可能な記録媒体を含むコンピュータプログラム製品であって、当該プログラムが、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしを含み、前記複合塗りつぶしは、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含むグループ化オブジェクトを形成するためのコードと、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングするためのコードと、
を備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、画像処理に関し、特に、複数のグラフィカルオブジェクトをレンダリングする方法に関する。また、本発明は、複数のグラフィカルオブジェクトをレンダリングする方法及び装置、並びに複数のグラフィカルオブジェクトをレンダリングするためのコンピュータプログラムが記録されたコンピュータ可読媒体を含むコンピュータプログラム製品に関する。
【背景技術】
【０００２】
ワードプロセッサなどの従来のソフトウェアアプリケーションは、ページ単位の文書を作成する。ページ単位の文書においては、各々のページが１つ以上のグラフィカルオブジェクト（すなわち、テキスト、行、塗りつぶし領域（fill reagions)及び／又は画像データ）を含む。そのような文書を表示装置又は印刷装置において表現する場合、ソフトウェアアプリケーションは、通常、表示装置又は印刷装置へ指令を送信する。それらの指令は、通常、グラフィカルインタフェースサービス(graphics interface services )により定義される。グラフィカルインタフェースサービスは、そのソフトウェアアプリケーションを実行しているネイティブオペレーティングシステムと関連する。そのようなオペレーティングシステムの１つがＷｉｎｄｏｗｓ（登録商標）である。Ｗｉｎｄｏｗｓ（登録商標）オペレーティングシステムのグラフィカルインタフェースサービスは、通常、グラフィックスデバイスインタフェース（ＧＤＩ：graphics device interface ）レイヤと呼ばれる。ＧＤＩレイヤは、オペレーティングシステムにより実行されるべきアプリケーションプログラミングインタフェース（ＡＰＩ：application programming interface ）として実現されてもよい。ＡＰＩは、オペレーティングシステムにより実行されるべきソフトウェアアプリケーションに、豊富な図形特徴セットを提供する。
【０００３】
通常、グラフィックスレンダリングシステムは、オペレーティングシステムのＧＤＩレイヤから受信されたグラフィカルオブジェクト（図形オブジェクト）をレンダリングし、画素を生成する。レンダリングは、ＧＤＩレイヤから受信されたグラフィカルオブジェクトをグラフィックスレンダリングシステムにより画素に変換するプロセスである。グラフィックスレンダリングシステムにより生成された画素は、その後、表示及び／又は印刷のために、出力装置へ送信される。
【０００４】
図１は、従来のソフトウェアアプリケーション１１０と、グラフィックスデバイスインタフェースレイヤ１２０と、グラフィックスレンダリングシステム１３０と、ターゲットデバイス１４０との関係を示す。アプリケーション１１０は、１つの文書の各ページを、一連の指令として送信する。レンダリングされるページごとに、一連の指令は、そのページのグラフィカルオブジェクトを記述するグラフィックインタフェースサービスによって定義される。ＧＤＩレイヤ１２０は、アプリケーションプログラム１１０とターゲットデバイス１４０との間を仲介する。ＧＤＩレイヤ１２０の存在によって、グラフィックスレンダリングシステム１３０は、Ｗｉｎｄｏｗｓ（登録商標）オペレーティングシステムが処理できるより、はるかに小さな機能性のセットを支援することが可能である。また、ＧＤＩレイヤ１２０は、グラフィックスレンダリングシステム１３０において最も効率がよいとＧＤＩレイヤ１２０が判定するフォーマット及びターゲットデバイス１４０の分解能で、グラフィカルオブジェクトをグラフィックスレンダリングシステム１３０に提供する。そこで、グラフィックスレンダリングシステム１３０は、ＧＤＩレイヤ１２０から受信されたグラフィカルオブジェクトをレンダリングし、画素を生成する。グラフィックスレンダリングシステム１３０により生成された画素は、その後、ターゲットデバイス１４０へ送信される。
【０００５】
グラフィックスソフトウェアアプリケーションには、多様な種類が存在する。それらのグラフィックスソフトウェアアプリケーションの多くは、複雑なグラフィカルオブジェクトの生成が可能である。通常、これらのオブジェクトは、特定のグラフィックスソフトウェアアプリケーションに特有のものである。例えば、Corel Draw（登録商標）と呼ばれる周知のグラフィックスソフトウェアアプリケーションは、「fountain fill（インクだめ塗りつぶし）」として知られる複雑なオブジェクトを作成できる。「fill（塗りつぶし）」は、グラフィカルオブジェクトがペイントされる（すなわち、塗りつぶされる）ときの画素データを記述するために使用される。例えば、赤色の正方形は、赤色フラット着色塗りつぶしを有する。fountain fillは、オブジェクトの２つ以上の色が互いに滑らかに流れ込むようなオブジェクトの塗りつぶしを記述する「勾配塗りつぶし」の１種である。勾配塗りつぶしには、数多くの型（例えば、線形、円錐形、放射及び非線形）がある。放射勾配塗りつぶしによって塗りつぶされたオブジェクト２１０が、図２Ａに示される。通常、勾配塗りつぶしの遷移は、１つの色が別の色に流れ込むことにより構成される。しかし、より複雑な勾配塗りつぶしは、多数の異なる色の間の多数の遷移を有するであろう。図２Ｂは、多数の遷移を有する勾配塗りつぶしによって塗りつぶされたオブジェクト２２０の一例を示す。
【０００６】
線形勾配塗りつぶしによってオブジェクトを塗りつぶすために、特定のグラフィックスソフトウェアアプリケーションにより，どの方法が使用されるかは、その特定のグラフィックスソフトウェアアプリケーションによって異なる。しかし、線形勾配塗りつぶしによってオブジェクトを塗りつぶす周知の方法の１つは、塗りつぶされるべきグラフィカルオブジェクトの境界規定ボックスの両端部において、開始色及び終了色を指定し、開始色と終了色の間を補間する工程を含む。
【０００７】
オブジェクト２１０及び２２０のような複雑なグラフィカルオブジェクトは、通常、プリンタドライバ又はディスプレイドライバにより直接にレンダリングされることが不可能である。従って、ＧＤＩレイヤは、通常、複数の平行四辺形の形態をとる複数のフラット塗りつぶし隣接オブジェクト（flat filled adjacent objects）として、勾配塗りつぶし（gradient fills ）をグラフィックスレンダリングシステムへ送信する。それらのフラット塗りつぶし隣接平行四辺形（flat filled adjacent parallelograms ）を使用することにより、グラフィックスレンダリングシステムは、アプリケーションに特有のグラフィックス型を支援する必要なく、複雑なグラフィカルオブジェクトをレンダリングすることができる。Painters Algorithmレンダリング方法を使用するレンダラの場合、フラット塗りつぶし平行四辺形は、フレーム記憶装置にレンダリングされてもよい。しかし、通常、ＧＤＩレイヤにより、線形勾配塗りつぶしと非線形勾配塗りつぶし（non-linear gradient fills ）の双方がフラット塗りつぶし平行四辺形として送信されるため、２つの隣接する平行四辺形の幅は、通常、一貫していない。その結果、それらの平行四辺形の連続するセットの間の色の変化は、必ずしも線形にはならない。
【０００８】
グラフィックスレンダリングシステム（図形レンダリングシステム）によっては、レンダリングプロセスは、２段階プロセスになる場合がある。そのようなレンダリングシステムにおいては、レンダリングされるべきページのグラフィカルオブジェクトは、レンダリングプロセスが始まる前に、まず、中間フォーマットに変換される。この中間フォーマットは、「ディスプレイリスト（display list）」として知られている。そのようなグラフィックスレンダリングシステムの１つにおいては、レンダリングプロセスの第１段階は、関連するオペレーティングシステムから受信されたページの各グラフィカルオブジェクトを、中間稜線ベースオブジェクト（intermediate edge-based object）に変換する。例えば、図３は、受信された各グラフィカルオブジェクトを中間稜線ベースオブジェクトに変換する従来のグラフィックスレンダリングシステム３３０を示す。図３の例では、グラフィックスアプリケーション３１０により作成され、且つ、複雑なグラフィカルオブジェクトに対応する線形勾配塗りつぶし（linear gradient fill ）３７０は、多数のフラット着色矩形（flat coloured rectangles ）（例えば、フラット着色矩形３８０）として、グラフィックスデバイスインタフェース３２０から、グラフィックスレンダリングシステム３３０へ送信される。グラフィックスレンダリングシステム３３０のディスプレイリスト作成モジュール３４０は、各々のフラット着色矩形３８０を２つの稜線、レベル及び塗りつぶしデータに変換する。それらの稜線、レベル及び塗りつぶしデータは、データベース（例えば、３８１、３８２及び３８３にそれぞれ）格納される。稜線は、各フラット着色矩形３８０が塗りつぶされるエリアを記述する。塗りつぶしデータは、フラット着色矩形３８０の稜線の内側における画素の色／不透明度を規定する。塗りつぶしデータは、フラット色、ビットマップ、式、又はフラット着色矩形３８０の中の特定の位置における画素データを記述するパターンであってもよい。レベルは、フラット着色矩形３８０のZ-オーダー（Z-order）、塗りつぶしデータに適用されるべきラスタ演算及び関連する稜線がクリッピング稜線であるか、又は塗りつぶし稜線であるかなどの重要なレンダリング情報を含む。
【０００９】
グラフィックスレンダリングシステム３３０がフラット着色矩形３８０のうちの１つをレンダリングする前に、特定の矩形の全ての稜線がｙの昇順で分類され、続いてｘの昇順で分類されるように、各矩形は分類されなければならない。ｙ座標及びｚ座標は、それぞれ、ラスタ化レンダリングシステム（rasterized rendering system）における走査線と、各走査線上の画素位置に対応する。グラフィックスレンダリングシステムは、稜線及びそれらに関連する塗りつぶし優先順位（Z-order）から成るディスプレイリスト３５０と共に、稜線がクリッピング稜線（clipping edge ）であるか、又は塗りつぶし稜線（filling edge）であるかなどの他の情報を生成する。
【００１０】
ディスプレイリスト３５０は、ジョブと呼ばれる場合もある。ジョブは、ページをレンダリングするために、グラフィックスレンダリングシステム３３０のレンダリングモジュール３６０により必要とされる全ての情報を含む。レンダリングモジュール３６０によるページのレンダリングは、レンダリングプロセスの第２段階である。
【００１１】
レンダリングモジュール３６０は、ジョブをパージング（parses）し、ページに沿って走査線ごとに、プリンタなどの下流側デバイスに対して画素を生成する。走査線ごとに、レンダリングモジュール３６０が着色矩形（例えば、矩形３８０）の左側稜線に至たる（encounters）と、レンダリングモジュール３６０は、その矩形と関連するレベルを中間バッファにロードする。矩形と関連するレベルは、この時点で、アクティブ状態になったという。レンダリングモジュール３６０が矩形の右側稜線に至った（encounters）とき、矩形と関連するレベルは非アクティブ状態（deactivated）になる。
【００１２】
レンダリングモジュール３６０は、本明細書において後に説明されるように、稜線に関して様々に異なる種類のアクティべーションルール（activation rules ）を使用できる。走査線上の各稜線セットの間の画素スパンは、それらのルールに従ってレンダリングされる。レンダリングモジュール３６０が１つの稜線に至ると、レンダリングモジュール３６０は、最上位（すなわち、最大Z-オーダー位置（greatest z-order position））の、現在アクティブ状態であるレベルを判定し、最上位の現在アクティブ状態のレベルの塗りつぶしデータに従って、画素をレンダリングする。最上位レベルに対応するオブジェクト（例えば、フラット着色矩形（flat filled rectangle））が透明である場合、下位のｚ-orderのレベルの合成を使用して、結果として得られる画素データが計算される。レンダリングモジュール３６０が稜線に至るたびに、全ての稜線は、次の走査線上の新たな位置に更新されなければならない。更に、稜線は互いに交差する場合もあるので、稜線がｘの昇順のままであることを保証するために、稜線も分類されなければならない。ページ上の全ての画素がレンダリングされるまで、レンダリングプロセスは走査線ごとに継続される。
【００１３】
先に説明したように、複雑なオブジェクトは、通常、グラフィックスデバイスインタフェース３２０により、フラット塗りつぶし矩形のような、より単純なオブジェクトに分解される。それらの単純なオブジェクトの各々は、別個に中間形態（intermediate form ）に変換されなければならないため、その変換には、相当に長い時間を要する。個別のフラット塗りつぶしオブジェクトをレンダリングするとき、オブジェクトの各々の稜線が分類されなければならず、また、走査線ごとに、各稜線が更新されなければならない。これも、レンダリングモジュール３６０には、長い時間を要するプロセスである。そのため、数百個もの単純なオブジェクトの分解された複雑なオブジェクトの場合には、各オブジェクトを中間稜線ベースフォーマット（intermediate edge based format ）に変換し、稜線ベースレンダリングモジュールを使用して、複雑なオブジェクトをレンダリングするプロセスの効率は、きわめて低い。
【００１４】
一例として、図２Ｃに示される水平方向線形勾配塗りつぶし（horizontal linear gradient fill ）２３０は、グラフィックスレンダリングシステム３３０へ送信される前に、グラフィックスデバイスインタフェース３２０により、２５６個のフラット塗りつぶし矩形に分解される。勾配塗りつぶし（gradient fill ）２３０が左から右、又は右から左へ進む最悪のケースでは、１本の走査線の上で、２５６個のフラット塗りつぶし（flat fills）の全てがアクティブ状態になる。これは、走査線ごとに、稜線の数が５１２あることと同等である。従って、稜線ベースレンダリングシステムの場合、走査線ごとに実行されることが必要な稜線の分類及び追跡の量が多くなるため、このようなレンダリング方法の効率は相当に低くなる。加えて、各々のフラット塗りつぶしが中間オブジェクトグラフィックスフォーマットで格納されなければならず、レンダリングを開始できる前に、各走査線の塗りつぶしパスごとに、塗りつぶしがアクセスされ、その後、全ての稜線が分類されなければならない。
【００１５】
上述のレンダリング方法では、処理されるべきフラット塗りつぶしの数が何千にも達した場合、大量のメモリアクセスが要求され、また、大量の塗りつぶし資源が消費される可能性がある。Ａ３より大判のページを高分解能で印刷するときには、そのように大量なフラット塗りつぶしが頻繁に起こる。
【００１６】
勾配塗りつぶし２３０をレンダリングするときに、稜線ベースレンダリングモジュール３６０のレンダリング性能を向上する方法の１つは、稜線更新の回数及び実行される必要がある稜線分類の量を減少することである。稜線更新及び稜線分類を減少する周知の方法の１つは、複数のグラフィカルオブジェクトをより大きな１つのグラフィカルオブジェクトにコンパイルするか、又はレンダリングモジュールが処理可能であるより複雑なオブジェクトにコンパイルすることにより、可能な部分で冗長稜線を除去する。複数のグラフィカルオブジェクトをより大きな１つのグラフィカルオブジェクトとしてコンパイルする多くの方法が、知られている。例えば、別個の２つの隣接するビットマップを互いにつなぎ合わせて、１つの大きなビットマップを形成してもよい。また、同一の色を有する２つの連続するフラット塗りつぶしを組み合わせて、より大きな１つのフラット塗りつぶしを生成してもよいし、線形勾配塗りつぶしを表現する連続するフラット塗りつぶしプリミティブを組み合わせて、グラフィックスレンダリングシステムによりレンダリング可能な型の１つの複雑な線形勾配塗りつぶしを形成してもよい。しかし、これらの周知のレンダリング方法は、全て、欠点や限界を有する。
【００１７】
例えば、連続するオブジェクトを組み合わせることを試みる周知のレンダリング方法は、特定のレンダリングモジュールで利用可能な指定の塗りつぶし型に限定される。従って、組み合わせ可能なオブジェクトは、互いに全く同一の塗りつぶし型を有するオブジェクトのみである。ＧＤＩ３２０のようなＧＤＩレイヤは、そのようなオブジェクトを分解する必要が始めからないので、この種のオブジェクトが頻繁に現れることはない。
【００１８】
ビットマップを組み合わせる方法の場合には、２つの異なるビットマップを１つのビットマップとして組み合わせるために、画像塗りつぶしデータ全体がコピーされなければならない。特に、多くのビットマップが多数のメモリ割り当てとして含まれ、大量の画像データコピーを実行する必要がある場合、画像塗りつぶしデータをコピーするプロセスは、容易に進まない可能性がある。
【００１９】
フラット塗りつぶしプリミティブを複雑な等価の塗りつぶしとして組み合わせるレンダリング方法は、特定のレンダリングモジュールにより支援される塗りつぶしを出力することに限定される。特定のレンダリングモジュールにより支援されると考えられる塗りつぶしの１つは、線形勾配塗りつぶしである。これは、通常、２つ又は３つの点により表現され、それらの点における色値に対応している。
【００２０】
先に説明したように、平行四辺形の幅が一貫せず且つ色の変化が一定ではないような、複数のフラット塗りつぶし平行四辺形として、勾配塗りつぶしをＧＤＩ３２０が送信することは珍しくない。線形ではない勾配塗りつぶし（例えば、図５Ａに示されるような非線形勾配塗りつぶし５１０）の場合、周知のレンダリング方法は、個々のフラット塗りつぶし平行四辺形を等価の線形勾配成分として組み合わせようとする。非線形勾配塗りつぶしオブジェクトを線形勾配塗りつぶしにコンパイルする周知のレンダリング方法は、２つの線形勾配塗りつぶしを生成するのが理想的である。図５Ｂは、図５Ａの非線形勾配塗りつぶし５１０から生成された２つの線形勾配塗りつぶし５２０及び５２５を示す。非線形勾配塗りつぶし５１０を与えられた場合、ＧＤＩ３２０により生成される平行四辺形の色の変化は一定ではなく、平行四辺形の幅も一貫していないため、勾配塗りつぶしをコンパイルする周知の方法は、勾配塗りつぶし５１０中の一貫性の欠如に対応することができず、図５Ｂのような理想的な結果を生成しない。
【００２１】
従来のレンダリング方法は、多くの場合、図５Ｃに示されるような多数の線形勾配塗りつぶし（linear gradient fills）５３０〜５３７を生成する。そのような多数の線形勾配塗りつぶしを生成するプロセスは、元のフラット塗りつぶし表現と比較して効率が悪く、最終的には、レンダリングモジュールの動作を遅くしてしまう。レンダリングモジュールの動作速度が低下するのは、フラット塗りつぶしの画素データと比較して、線形勾配塗りつぶしの画素データを計算するほうが困難であるためと、通常、除去されるのが最小限の稜線にとどまるためである。その結果、最終的には、レンダリング速度（rendering speed）が実際に低下する。ＧＤＩ３２０から受信される勾配塗りつぶしを表現するフラット塗りつぶし（例えば、フラット塗りつぶし矩形３８０）は、必ずしも一貫しておらず、常に正当な線形色変化限界（linear colour change limits）を有しているとは限らない。従って、従来のレンダリング方法は、フラット塗りつぶしを効率よく処理するという点で、非常に大きな制限を有する。更に、従来のレンダリング方法と関連するレンダリングモジュールは、図形プリミティブを完全に最適化するために利用可能な機能性を備えていないため、従来のレンダリング方法には、そのような最適化能力が欠けている。
【００２２】
線形勾配塗りつぶしをレンダリングすることのもう１つの欠点は、ページ上にカラー画像を生成するために、プリンタがシアン、マゼンタ及び黄色（ＣＭＹ）の減法混色の３原色と、黒（Ｋ）とを使用するために起こる。その結果、ＲＧＢ色空間で格納された線形勾配塗りつぶしを、ＣＭＹＫ色空間に変換することが必要である。ＲＧＢ色空間からＣＭＹＫ色空間への線形勾配塗りつぶしの変換は、ホストコンピュータ内で実行されるか、又はターゲットデバイスで実行されることが可能である。しかし、各々がＲＧＢ色空間で対応する色値を有する２つ又は３つの点によって記述される線形勾配塗りつぶしは、単純に各々の点の色を変換するだけでは、色変換不可能である。それは、ＧＤＩにより提供される元の色データが、色変換後の色空間に線形マッピングされないからである。すなわち、ＲＧＢ色空間とＣＭＹＫ色空間との間に、線形関係は存在しない。線形勾配塗りつぶしを色変換する従来の方法は、塗りつぶし中の画素ごとに、画素データのＲＧＢ値を判定する。その後、線形勾配塗りつぶし中の各々の画素は、等価のＣＭＹＫ色値に変換される。色変換後の線形勾配塗りつぶしは、次に、ビットマップとしてディスプレイリストに追加される。従って、線形勾配塗りつぶしをＲＧＢ色空間に格納することは、非常に効率が悪い。
【００２３】
従って、グラフィカルオブジェクトをレンダリングする、更に効率のよい方法が必要であることは明らかである。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
本発明の目的は、既存の構成の１つ以上の欠点を実質的に克服すること、又は少なくとも改善することである。
【課題を解決するための手段】
【００２５】
本発明の１つの面によれば、各々が所定のオブジェクトアウトラインと、所定のZ-オーダー（Z-order）と、関連する塗りつぶしとを含み、特定のオブジェクトに関するオブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングする方法は、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしを含み、前記複合塗りつぶしが、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含む、グループ化オブジェクトを形成する工程と、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングする工程と、
を備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とする。
【００２６】
本発明の別の面によれば、グラフィカルオブジェクトが、所定のオブジェクトアウトラインと、前記複合塗りつぶしと含み、当該所定のオブジェクトアウトラインは、前記グラフィカルオブジェクトが塗りつぶされるエリアを定義する、当該グラフィカルオブジェクトをレンダリングするための複合塗りつぶし方法は、
前記複合塗りつぶしは、レンダリング時に前記グラフィカルオブジェクトが塗りつぶされるべき形式を定義する複数の塗りつぶしを含むデータ構造として構成されることを特徴とする。
【００２７】
本発明の更に別の面によれば、各々が所定のオブジェクトアウトラインと、所定のZ-オーダー（Z-order）と、関連する塗りつぶしと含み、特定のオブジェクトのオブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングする装置は、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしを含み、前記複合塗りつぶしは、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含む、グループ化オブジェクトを形成するための組み合わせ手段と、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングするレンダリング手段と、
を備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とする。
【００２８】
本発明の更に別の面によれば、各々が所定のオブジェクトアウトラインと、所定のZ-オーダー（Z-order）と、関連する塗りつぶしを含み、特定のオブジェクトに関する当該オブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングするためのコンピュータプログラムであって、当該コンピュータプログラムが、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしと含み、前記複合塗りつぶしは、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含むグループ化オブジェクトを形成するためのコードと、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングするためのコードと、
備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とする。
【００２９】
本発明の更に別の面によれば、各々が所定のオブジェクトアウトラインと、所定のZ-オーダー（Z-order）と、関連する塗りつぶしを含み、特定のオブジェクトのオブジェクトアウトラインは、前記特定のオブジェクトが塗りつぶされるエリアを定義する、複数のグラフィカルオブジェクトをレンダリングするためのコンピュータプログラムを記録したコンピュータで読み取り可能な記録媒体を含むコンピュータプログラム製品であって、当該プログラムが、
前記オブジェクトの各々を組み合わせて、グループ化オブジェクトアウトラインと、関連する複合塗りつぶしを含み、前記複合塗りつぶしは、前記グラフィカルオブジェクトと関連する塗りつぶしを表現する１つ以上の塗りつぶしデータ構造を含むグループ化オブジェクトを形成するためのコードと、
前記グループ化オブジェクトアウトラインに従って、前記グループ化オブジェクトをレンダリングするためのコードと、
を備え、前記グループ化オブジェクトをレンダリングするために使用される１つ以上の塗りつぶしは、前記複合塗りつぶしに従って判定されることを特徴とする。
【００３０】
本発明の他の面も開示される。
【発明を実施するための最良の形態】
【００３１】
添付の図面のうちの１つ以上において、同一の図中符号を有するステップ及び／又は特徴を参照するとき、本明細書の便宜上、それらのステップ及び／又は特徴は、特に指示のない限り、同一の機能又は動作を有するものとする。
【００３２】
「背景技術」の章及び前述の従来技術の構成に関連する部分に含まれる説明は、それぞれ対応する刊行物及び／又は使用を通して公の知識を形成する文書又は装置の説明に関することに注意すべきである。それらは、そのような文書又は装置が何らかの形で当該技術分野における共通の一般知識の一部を形成するという、本発明の発明者又は特許出願人による表明として解釈されるべきではない。
【００３３】
以下、図１から図１６を参照して、複数のオブジェクトを組み合わせる方法９００（図９を参照）を説明する。方法９００は、１組の連続するグラフィカルオブジェクトを効率よく組み合わせて、連続するグラフィカルオブジェクトの組み合わせを表現するハイレベルコンパイルドオブジェクトを生成する。コンパイルドオブジェクトは、「グループ化」オブジェクトと呼ばれてもよい。そのような連続するグラフィカルオブジェクトが異なる塗りつぶし型を有する場合であっても、オブジェクトを組み合わせるために、方法９００が使用されてよい。方法９００は、コンパイルドオブジェクトをディスプレイリストへ出力する。
【００３４】
コンパイルドオブジェクトは、関連するメタ塗りつぶし（meta-fill ）を有する。メタ塗りつぶしは、コンパイルドオブジェクトと関連する塗りつぶしの集合体を記述するために使用される複合塗りつぶし（compound fill）である。以下に詳細に説明されるように、メタ塗りつぶしは、メタ塗りつぶしに関する情報を定義するためのヘッド構造を含む。ヘッド構造の次に、コンパイルドオブジェクトの塗りつぶしを記述する塗りつぶし構造の連係リストが続く。連係リストの大きさを最小限にするために、コンパイルドオブジェクトの複数の塗りつぶしは、１つの単純な複合塗りつぶし又は複雑な塗りつぶしとして組み合わされてもよい。
【００３５】
メタ塗りつぶしは、並列して位置する１組の単純な基本オブジェクト（プリミティブ）を組み合わせて、１つの複雑な基本オブジェクトを形成するために使用されてもよい。従って、この場合、１組のプリミティブを表現するために要求される稜線は、２つだけである。メタ塗りつぶしは、グラフィックスインタフェースが多数のフラット塗りつぶしにより表現していた非線形ブレンド（non-linear blends）のような、複雑な描画オブジェクトを再度合体することにより、レンダリング時間を短縮する。例えば、非線形勾配塗りつぶし５１０に類似するメタ塗りつぶしは、図５Ｃの線形勾配塗りつぶし５３０〜５３７から形成されてもよい。そのようなメタ塗りつぶしは、図５Ｃの線形勾配塗りつぶし５３０〜５３７と比較して大幅に改善されている。
【００３６】
メタ塗りつぶし（meta-fill）は、例えば、ＧＤＩ３２０のようなＧＤＩにより提供される情報を変更しない。しかし、２つのオブジェクトが重複する場合、メタ塗りつぶしは、オブジェクトの閉塞する部分を除去する。塗りつぶしをメタ塗りつぶしに変換する際に、情報は実質的に全く失われない。基本塗りつぶしがメタ塗りつぶしとして組み合わせられるときに、描画出力が一貫したままであり且つ影響を受けないことを保証するために、メタ塗りつぶしを形成するために使用される１つ以上の基本塗りつぶしの全ての情報は保持される。これとは対照的に、従来の方法は、色情報に影響を及ぼすため、出力が入力を反映することが保証されることは全くない。更に、メタ塗りつぶしは、稜線オーバヘッド（edge overhead）を減少する。
【００３７】
ＰＤＬを生成するレンダリングシステムの場合、メタ塗りつぶしは、基本オブジェクトを表現するために要求されるＰＤＬの大きさを縮小する。ＰＤＬの大きさが縮小されると、ＰＤＬの送信が要求される処理は改善される。
【００３８】
メタ塗りつぶしは、フラット塗りつぶし、線形勾配塗りつぶし及びビットマップを使用して形成されてもよい。これに対し、従来のレンダリングシステムは、通常、色混合（color blends）を表現するフラット塗りつぶしを認識するだけである。
【００３９】
コンパイルドオブジェクトは、メタ塗りつぶしをリアルタイムで復号することにより、関連するメタ塗りつぶしを使用して、効率よくレンダリングされる。図１から図１６を参照して、コンパイルドオブジェクトをレンダリングする方法１０００（図１０を参照）も説明される。
【００４０】
ここで説明される方法は、図４に示されるような汎用コンピュータシステム４００を使用して実現されてもよい。その場合、図１から図１６を参照して説明されるプロセスは、コンピュータシステム４００内部で実行されるコードモジュールのようなソフトウェアとして実現されてもよい。特に、説明される方法のステップは、ソフトウェアにおいて、コンピュータにより実行される命令により実行される。それらの命令は、各々が１つ以上の特定のタスクを実行する１つ以上のコードサブモジュールとして形成されてもよい。ソフトウェアは、例えば、以下に説明される記憶装置を含むコンピュータ可読媒体に格納されてもよい。ソフトウェアは、コンピュータ可読媒体からコンピュータにロードされ、その後、コンピュータにより実行される。そのようなソフトウェア又はコンピュータプログラムが記録されたコンピュータ可読媒体は、コンピュータプログラム製品である。コンピュータプログラム製品をコンピュータにおいて使用することにより、説明される方法を実現するための好都合な装置が獲得されるのが好ましい。
【００４１】
コンピュータシステム４００は、コンピュータモジュール４０１、キーボード４０２及びマウス４０３などの入力装置、並びにプリンタ４１５、表示装置４１４及びスピーカ４１７などの出力装置により形成される。変復調器（モデム）トランシーバ装置４１６は、例えば、電話回線４２１又は他の機能媒体を介して接続可能である通信ネットワーク４２０と通信するために、コンピュータモジュール４０１により使用される。モデム４１６は、インターネット、並びにローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）などの他のネットワークシステムへのアクセスを獲得するために使用可能である。また、実現形態によっては、モデム４１６は、コンピュータモジュール４０１に組み込まれてもよい。
【００４２】
コンピュータモジュール４０１は、通常、少なくとも１つのプロセッサユニット４０５と、例えば、半導体ランダムアクセスメモリ（ＲＡＭ）及び読み取り専用メモリ（ＲＯＭ）から構成されるメモリユニット４０６とを含む。コンピュータモジュール４０１は、ビデオディスプレイ４１４及びスピーカ４１７に結合するオーディオビデオインタフェース４０７と、キーボード４０２及びマウス４０３、並びにオプションとして使用されるジョイスティック（図示せず）に対応する入出力（Ｉ／Ｏ）インタフェース４１３と、モデム４１６及びプリンタ４１５に対応するインタフェース４０８とを含む複数のＩ／Ｏインタフェースを更に含む。実現形態によっては、モデム４１６は、コンピュータモジュール４１０の内部、例えば、インタフェース４０８の中に組み込まれてもよい。記憶装置４０９が設けられる。通常、記憶装置４０９は、ハードディスクドライブ４１０及びフロッピー（登録商標）ディスクドライブ４１１を含む。磁気テープドライブ（図示せず）が更に使用されてもよい。ＣＤ‐ＲＯＭドライブ４１２は、通常、不揮発性データ源として設けられる。コンピュータモジュール４０１の構成要素４０５〜４１３は、通常、相互接続バス４０４を介して、コンピュータシステム４００が当業者に知られている従来の動作モードで動作する結果となるように互いに通信する。説明される構成を実施できるコンピュータの例としては、ＩＢＭ‐ＰＣ及びそのコンパチブル、Sun Sparcstation又はそれらから派生した類似のコンピュータシステムがある。
【００４３】
通常、コードモジュールは、ハードディスクドライブ４１０に常駐し、プロセッサ４０５に読み取られ、その実行は、プロセッサ４０５により制御される。モジュール及びネットワーク４２０から取り出されるデータの中間格納は、可能であれば、ハードディスクドライブ４１０と協調して、半導体メモリ４０６を使用して実現されてもよい。場合によっては、コードモジュールは、ＣＤ‐ＲＯＭ又はフロッピー（登録商標）ディスクに符号化された形でユーザに供給され、対応するドライブ４１２又は４１１を介して読み取られてもよい。あるいは、コードモジュールは、ユーザにより、ネットワーク４２０からモデム装置４１６を介して読み取られてもよい。更に、ソフトウェアは、他のコンピュータ可読媒体からコンピュータシステム４００にロードされることも可能である。ここで使用される用語「コンピュータ可読媒体」は、実行及び／又は処理のために、命令及び／又はデータをコンピュータシステム４００に提供することに関与するあらゆる記憶媒体又は送信媒体を表す。記憶媒体の例としては、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ‐ＲＯＭ、ハードディスクドライブ、ＲＯＭ又は集積回路、光磁気ディスク、あるいはＰＣＭＣＩＡカードなどのコンピュータ可読カードがあり、それらの装置は、コンピュータ４０１の内部にあってもよいし、外部にあってもよい。送信媒体の例としては、無線送信チャネル又は赤外線送信チャネル、並びに別のコンピュータ又はネットワーク化装置へのネットワーク接続、更には、Ｅメール送信及びウェブサイトなどに記録された情報を含めたインターネット又はイントラネットがある。
【００４４】
あるいは、説明される方法は、説明される方法の機能又は部分機能を実行する１つ以上の集積回路などの専用ハードウェアで実現されてもよい。そのような専用ハードウェアには、グラフィックプロセッサ、デジタルシグナルプロセッサ、又は１つ以上のマイクロプロセッサ及び関連メモリが含まれる。
【００４５】
方法９００は、連続するグラフィカルオブジェクトを組み合わせるために使用されてもよい。それらのグラフィカルオブジェクトは、元来、１つの複雑なオブジェクトに由来するか、並列して位置する２つのオブジェクトであるか、又は重複する２つのオブジェクトである。図６は、２段階稜線ベースグラフィックスレンダリングシステム６３０の一例を示す。このレンダリングシステム６３０は、方法９００及び方法１０００を実現するために使用されてもよい。グラフィックスレンダリングシステム６３０は、図６に示される線形勾配塗りつぶし６９０のような線形勾配塗りつぶしをレンダリングするために使用されてもよい。グラフィックスレンダリングシステム６３０は、オブジェクトコンパイラ６７０と、メタ塗りつぶしディスパッチャ６８０とを具備する。グラフィックスレンダリングシステム６３０は、ディスプレイリスト作成モジュール６４０と、ディスプレイリスト６５０と、レンダリングモジュール６６０とを更に具備する。図６に示されるように、グラフィックスデバイスインタフェース６２０は、グラフィックスアプリケーション６１０から線形勾配塗りつぶし６９０を受信し、線形勾配塗りつぶし６９０を、複数の隣接するフラット塗りつぶしオブジェクト（例えば、平行四辺形６２１）として、グラフィックスレンダリングシステム６３０へ送信する。
【００４６】
オブジェクトコンパイラ６７０は、隣接するオブジェクト、重複するオブジェクト又は連続するオブジェクトを組み合わせ、関連するメタ塗りつぶしと共にコンパイルドオブジェクトを適宜形成し、それにより、そのようなオブジェクトの間にある稜線を除去するために使用されてもよい。現在のコンパイルドオブジェクトとして組み合わせできるオブジェクトがそれ以上存在しないとオブジェクトコンパイラ６７０が判定したならば、コンパイラ６７０は、コンパイルドオブジェクトを稜線、レベル及び関連するメタ塗りつぶしに変換してもよい。その後、コンパイルドオブジェクトは、現在のディスプレイリスト６５０に挿入されてもよい。
【００４７】
レンダリングモジュール６６０は、ディスパッチャ６８０を具備する。レンダリングモジュール６６０は、メタ塗りつぶしデータを復号し、塗りつぶし情報を生成する。その塗りつぶし情報は、コンパイルドオブジェクト６４１中の１つ以上の画素スパンをレンダリングするために使用されてもよい。
【００４８】
次に、図９を参照して、複数のオブジェクトを組み合わせる方法９００を説明する。方法は、ハードディスクドライブ４１０に常駐し、プロセッサ４０５により実行が制御されるソフトウェアとして実現されてもよい。方法９００は、コンパイラ６７０の１つ以上のソフトウェアモジュールとして実現されてもよい。オブジェクトは、グラフィックスデバイスインタフェース６２０のようなグラフィックスインタフェースから、ｚ-orderの昇順で、コンパイラ６７０により受信されてもよい。
【００４９】
方法９００は、ステップ９１０で始まる。ステップ９１０では、オブジェクトコンパイラ６７０を実行するプロセッサ４０５は、グラフィックスデバイスインタフェース６２０から受信された現在のオブジェクトを検出する。次のステップ９２０で、プロセッサ４０５は、現在のオブジェクトが単純なマージルール（merging rules）に従うか否かを判定する。それらのルールは、
（１）オブジェクトが２つの平行で、一致しない直線の辺を有すること、
（２）オブジェクトが、（１）で識別された２つの平行な辺の不特定の拡張（indefinite extension ）エリアの外に出ないことである。
【００５０】
現在のオブジェクトがそれらのルールに適合する場合、現在のオブジェクトはマージされてもよい。現在のオブジェクトがマージされてもよいならば、方法９００は、ステップ９３０へ進む。そうでない場合には、方法は、ステップ９４０へ進む。
【００５１】
ステップ９３０においては、プロセッサ４０５は、現在のオブジェクトをメモリ４０６に格納する。現在のオブジェクトは、この時点では、中間フォーマットに変換されない。次に、方法９００は、ステップ９５０へ進み、ステップ９１０で受信されたオブジェクトは、「以前に格納された」オブジェクトになる。
【００５２】
ステップ９４０では、プロセッサ４０５は、現在のオブジェクトを稜線ベースフォーマットに変換し、方法９００は、ステップ９５０に続く。次のステップ９５０で、プロセッサ４０５は、グラフィックスデバイスインタフェースから次のオブジェクトを受信する。ステップ９５０で受信されたオブジェクトが「現在」のオブジェクトになる。この時点で、それまでにフローチャートのどの経路をたどったかに応じて、「以前に格納された」オブジェクトは存在する場合もあるが、存在しない場合もある。
【００５３】
方法は、次のステップ９６０に続く。ステップ９６０では、以前に格納されたオブジェクトが存在するとプロセッサ４０５が判定した場合、方法９００は、ステップ９７０へ進む。そうでない場合には、方法９００は、ステップ９８０へ進む。
【００５４】
ステップ９７０で、プロセッサ４０５は、まず、現在のオブジェクトが先にステップ９２０に関連して挙げた単純なマージルールに従うか否かを判定することにより、現在のオブジェクトを先に格納されたオブジェクトと組み合わせてよいか否かを判定する。組み合わせてよいならば、プロセッサ４０５は、現在のオブジェクト及び以前に格納されたオブジェクトが所定の基準を満たすか否かを判定する。ステップ９７０の所定の基準は、次の通りである。
【００５５】
（１）現在のオブジェクトと以前に格納されたオブジェクトの双方の平行な辺が同一の角度であること、及び
（２）現在のオブジェクトと以前に格納されたオブジェクトが、それらのオブジェクトの平行な辺の全長にわたって重複するか、それらの平行な辺で互いに境を接していること。
【００５６】
図１５Ａから図１５Ｅは、上記の所定の基準を満たし、従って、組み合わせ可能なオブジェクトのいくつかの例（例えば、１５１１）を示す。図１５Ａは、上記の基準を満たすオブジェクト１５１１及び１５１０を示す。オブジェクト１５１１及び１５１０は、組み合わせの結果として得られるアウトライン１５１２を記述するために、パス（path）を形成することを要求しない。アウトライン１５１２は、４つの点により表現されてもよい。同様に、図１５Ｂは、上記の基準を満たすオブジェクト１５２０及び１５２２を示す。それらのオブジェクトは、組み合わせの結果として得られるアウトライン１５２１を記述するために、パスを要求しない。この場合も、アウトライン１５２１は、４つの点により表現されてもよい。
【００５７】
図１５Ｃは、上記の所定の基準を満たし、従って、組み合わせ可能なオブジェクト１５３０及び１５３２を示す。オブジェクト１５３０及び１５３２は、組み合わせの結果として得られるコンパイルドオブジェクト（compiled object ）１５３１を記述するために、パスを形成することを要求する。同様に、図１５Ｄは、上記の所定の基準を満たし、組み合わせ可能なオブジェクト１５４０及び１５４２を示す。オブジェクト１５４０及び１５４２は、組み合わせの結果として得られるコンパイルドオブジェクト１５４１を記述するために、パスを形成することを要求する。同様に、図１５Ｅは、上記の所定の基準を満たし、組み合わせ可能な２つのオブジェクト１５５０及び１５５２を示す。オブジェクト１５５０及び１５５２は、組み合わせの結果として得られるコンパイルドオブジェクト１５５１を記述するために、パスを形成することを要求する。
【００５８】
これに対し、図１５Ｆ及び図１５Ｇは、上記の所定の基準を満たさず、組み合わせ不可能なオブジェクトのいくつかの例（例えば、１５７１）を示す。図１５Ｆは、上記の基準を満たさないために、組み合わせ不可能なオブジェクト１５６０及び１５６１の例を示す。特に、オブジェクト１５６０及び１５６１は、オブジェクトの平行な（水平方向の）辺により境界を規定されるエリアの外側に出ていることにより、単純なマージルールのうちの第２のルールに反する。同様に、図１５Ｇは、上記の基準を満たさないために、組み合わせ不可能なオブジェクト１５７０及び１５７１の例を示す。特に、オブジェクト１５７０及び１５７１は、平行である２つの一致しない辺を有していないことにより、単純なマージルールのうちの第１のルールに反する。
【００５９】
現在のオブジェクトと以前に格納されたオブジェクトがステップ９７０の所定の基準を満たすならば、方法９００は、ステップ９７１へ進む。ステップ９７１では、現在のオブジェクトは、以前に格納されたオブジェクトと共に、メモリ４０６に格納される。現在のオブジェクトと、以前に格納されたオブジェクトの塗りつぶしが同一で、フラット色から構成されている場合に、現在のオブジェクトは、以前に格納されたオブジェクトとマージされるのが好ましい。ステップ９７０で、現在のオブジェクトと、以前に格納されたオブジェクトを組み合わせ不可能な場合には、方法９００は、ステップ９９０へ進む。
【００６０】
ステップ９９０では、現在のオブジェクトを以前に格納されたオブジェクトと組み合わせ不可能であるため、以前に格納された全てのオブジェクトが組み合わされて、１つのコンパイルドオブジェクトが形成される。コンパイルドオブジェクトは、中間稜線ベースグラフックスフォーマットに変換され、その後、方法９００は、ステップ９８０へ進む。ステップ９９０で、オブジェクトを中間フォーマットに変換するとき、方法９００は、メモリ４０６内部に構成されたメタ塗りつぶし構造の中に塗りつぶし長さを格納する。塗りつぶし長さは、以前に格納されたオブジェクトの個々の塗りつぶしの水平方向ラン長さに対応する。以前に格納されたオブジェクトが２つ以上存在する場合、コンパイラ６７０は、ステップ９９０において、メタ塗りつぶし中の塗りつぶしを記述する基本塗りつぶしデータ構造（primitive fill data structures ）の連係リスト（linked list ）を作成することにより、メタ塗りつぶしを生成するのが好ましい。
【００６１】
図１１は、メタ塗りつぶし１１１０を詳細に示す。メタ塗りつぶし１１１０は、コンパイルドオブジェクトの中の任意の点における特定の塗りつぶしエントリ（particular fill entry ）を呼び出すために必要なデータの全てを含む。メタ塗りつぶし１１１０は、ヘッダ１１２０を含む。ヘッダ１１２０は、トラッキングポイント（tracking point ）１１２１及びトラッキングポイントＤＸ１１２２を含む。トラッキングポイント１１２１は、指定された走査線に関して、メタ塗りつぶし１１１０の中の第１の塗りつぶし１１２３の開始場所を指示するために使用されてもよい。指定された走査線に関して、メタ塗りつぶし１１１０の中の第１の塗りつぶしの開始場所を指示することにより、以下に更に詳細に説明されるように、メタ塗りつぶし１１１０と関連するコンパイルドオブジェクトをレンダリングすることができる。トラッキングポイント１１２１は、現在の走査線に対して、トラッキングポイントＤＸ１１２２に従って更新される。トラッキングポイントＤＸ１１２２は、メタ塗りつぶし１１１０により表現されるコンパイルドオブジェクトを形成するために、当初、グループ化されたオブジェクトの平行な辺の傾きを表す。トラッキングポイントは、オブジェクトの最も左側の平行な辺と、オブジェクトが存在している最上位置の走査線との交点として設定される。トラッキングポイントＤＸ１１２２は、メタ塗りつぶし１１１０の中の第１の塗りつぶしの場所を追跡するために、ディスパッチャ６８０により使用されてもよい。メタ塗りつぶしの中の第１の塗りつぶしの位置がわかれば、コンパイルドオブジェクトの他の全ての塗りつぶしを判定できる。ヘッダ１１２０は、次の塗りつぶし１１２３を指示するポインタ１１３３を更に含む。
【００６２】
個別の基本塗りつぶし（primitive fills ）１１２３は、連係リストとして、ヘッダ１１２０に付加される。個別の塗りつぶしの各々は、互いに連係され、各基本塗りつぶしは、ヘッダ（例えば、ヘッダ１１２９）を含む。ヘッダ１１２９は、メタ塗りつぶし１１１０の中の特定の塗りつぶしの画素ランの長さを表す少なくとも１つのサイズ変数１１３１を含む。サイズ変数１１３１は、メタ塗りつぶし１１１０を画素にレンダリングするときに、ディスパッチャ６８０により使用される。以下に更に詳細に説明されるように、サイズ変数１１３１は、メタ塗りつぶし１１１０の中の塗りつぶしごとに、正しい大きさの画素ランが出力されることを保証する。コンパイラ６７０は、メタ塗りつぶし１１１０に追加される各オブジェクトの平行な辺の間の水平方向距離を単純に判定することにより、メタ塗りつぶし１１１０の中の個別の塗りつぶしの画素長さを判定する。ヘッダ１１２９は、塗りつぶし型１１３５及び関連パラメータと、次の塗りつぶし１１２５を指示するポインタ１１３７とを更に含む。メタ塗りつぶし１１１０が生成されたならば、メタ塗りつぶし１１１０は、コンパイルドオブジェクトの稜線及びレベルデータと共に、ディスプレイリストに追加される。
【００６３】
他の実施形態においては、メタ塗りつぶしに、テーブル又はアレイなどの他のデータ構造が使用されることも可能であろう。
【００６４】
尚、ステップ９９０で作成されるコンパイルドオブジェクトのレベルは、最も早い時点（最低レベル）で先に格納されたオブジェクトのレベルと等しい。
【００６５】
方法９００は、次のステップ９８０に続く。ステップ９８０では、プロセッサ４０５は、ステップ９２０のときと同様に、現在のオブジェクトが単純なマージルールに従うか否かを判定する。現在のオブジェクトがステップ９７０で以前に評価されており、現在のオブジェクトを別のオブジェクトとマージしてもよいと判定されていた場合、プロセッサ４０５は、その解析結果を使用して、現在のオブジェクトをマージできるか否かを判定してもよい。ステップ９８０で、現在のオブジェクトを別のオブジェクトとマージしてもよいとプロセッサ４０５が判定した場合、方法９００は、ステップ９８１へ進む。そうでない場合には、方法９００は、ステップ９８５へ進む。ステップ９８５では、現在のオブジェクトは、中間フォーマットに変換される。その後、実行は、ステップ９８２へ進む。
【００６６】
ステップ９８１では、現在のオブジェクトは、メモリ４０６に格納される。次のステップ９８２において、グラフィックスレンダリングシステム６３０が処理すべきオブジェクトが他に存在しない場合、方法９００は、ステップ９８３へ進む。処理すべきオブジェクトが存在する場合には、方法９００は、ステップ９５０に戻る。ステップ９８３では、ステップ９９０のときと同様に、以前に格納された全てのオブジェクトが組み合わされて、コンパイルドオブジェクトが形成される。コンパイルドオブジェクトは、関連するメタ塗りつぶしと共に、中間稜線ベースフォーマットに変換される。
【００６７】
ステップ９９０及び／又は９８３において、コンパイルドオブジェクトの稜線及びレベルデータは、個別のオブジェクト（すなわち、以前に格納されたオブジェクト）の特性からではなく、コンパイルドオブジェクトのアウトラインから判定される。コンパイルドオブジェクトの中の塗りつぶしデータを記述するために、標準基本塗りつぶしではなく、メタ塗りつぶしが使用される。図１２は、コンパイルドオブジェクト１２１０の一例及び関連するメタ塗りつぶし１２１５を示す。
【００６８】
図７Ａは、当初の稜線ベースオブジェクト７１０を示す。図７Ｂは、従来の方式により、塗りつぶし７２０、稜線７２２及びレベル７２４として格納されたオブジェクト７１０を示す。これとは対照的に、図７Ｃに示されるように、オブジェクト７１０は、塗りつぶし７３０、稜線７３２及びレベル７３４により表現されるコンパイルドオブジェクトとして格納されてもよい。元のオブジェクト７１０を表現する図７Ｃの稜線７３２及びレベル７３４は、図７Ｂの稜線７２２及びレベル７２４ほどメモリを必要としない。
【００６９】
レンダリングモジュール６６０のディスパッチャ６８０は、特定の画素及び特定の走査線位置に対して、どの塗りつぶしをレンダリングすべきかを判定する。レンダリングされるべき最上位のアクティブレベルが、そのレベルと関連するメタ塗りつぶしを有する場合、ディスパッチャ６８０は、メタ塗りつぶしを復号するために使用されてもよい。
【００７０】
先に説明したように、メタ塗りつぶしは、ディスパッチャ６８０により追跡されるトラッキングポイント１１２１を含む。トラッキングポイント１１２１は、当初組み合わされたオブジェクトの平行な辺と平行に移動する。トラッキングポイント１１２１を使用して、ディスパッチャ６８０は、レンダリングされるべきコンパイルドオブジェクトの中の任意の位置に対して、メタ塗りつぶし１１１０の中でどの塗りつぶしを使用すべきかを判定してもよい。
【００７１】
コンパイルドオブジェクトの全体又は一部がレンダリングされるべき場合、コンパイルドオブジェクトを表現するレンダリング情報は、ディスパッチャ６８０へ送信される。ディスパッチャ８０は、レンダリングモジュール６６０の現在のｘ位置、コンパイルドオブジェクトのトラッキングポイント１１２１及びメタ塗りつぶし１１１０の中の個別の塗りつぶし（例えば、１１２３）の画素幅を使用して、現在の塗りつぶしと、現在の塗りつぶしからレンダリングされるべき画素の数とを判定する。メタ塗りつぶし１１１０の中のｘ位置は、走査線上で、トラッキングポイント１１２１と同一の点に対応するとは限らない。それは、メタ塗りつぶし１１１０を閉塞する他のオブジェクトが存在するか、又はメタ塗りつぶし１１１０がクリップオブジェクトを含む可能性があるためである。例えば、図１２は、クリッピング領域１２２０を伴うコンパイルドオブジェクト１２１０を示す。
【００７２】
図１０は、コンパイルドオブジェクトをレンダリングする方法１０００を示す流れ図である。方法１０００は、ハードディスクドライブ４１０に常駐し、プロセッサ４０５により実行を制御されるソフトウェアとして実現されてもよい。方法１０００は、ディスパッチャ６８０の１つ以上のソフトウェアモジュールとして実現されてもよい。方法１０００は、第１のステップ１０１０で始まる。ステップ１０１０で、ディスパッチャ６８０は、メタ塗りつぶしを受信する。メタ塗りつぶしは、レンダリングモジュール６６０から受信されてもよい。レンダリングモジュール６６０は、レンダリングされるべき画素の数、出力フォーマット及びレンダリングモジュールの現在の走査線位置を指定してもよい。また、レンダリングモジュール６６０は、レンダリングされた画素データを挿入するための、メモリ４０６内部の出力バッファを構成してもよい。
【００７３】
次に、方法１０００は、ステップ１０１５へ進む。ステップ１０１５では、レンダリングされるべき現在の走査線に従って、メタ塗りつぶしのトラッキングポイント（例えば、１１２１）が更新される。ディスパッチャ６８０は、メタ塗りつぶしのトラッキングポイントの現在のｙ位置と、現在の走査線のｙ位置との距離を判定することにより、メタ塗りつぶしのトラッキングポイントを更新する。次に、ディスパッチャ６８０は、判定された距離（０になる場合もある）をトラッキングポイントＤＸ（例えば、１１２２）と乗算する。次に、新たなトラッキングポイントｘ位置を判定するために、その乗算の結果は、現在のトラッキングポイントｘ位置に加算される。メタ塗りつぶしのトラッキングポイントの新たなｙ位置は、現在の走査線の現在のｙ位置と一致するように更新される。次のステップ１０２０で、レンダリングモジュール６６０の現在のレンダリング位置がメタ塗りつぶしのトラッキングポイントから離間している距離の画素数を判定するために、現在のレンダリング位置がトラッキングポイントと比較される。ステップ１０２０における判定は、更新後のトラッキングポイントｘ位置を現在のレンダリングｘ位置から減算することにより実行されてもよい。
【００７４】
方法１０００は、次のステップ１０３０に続く。ステップ１０３０で、プロセッサ４０５は、メタ塗りつぶしの塗りつぶしからアクティブ塗りつぶしを判定する。アクティブ塗りつぶしは、レンダリングされるべき現在の画素データに対応する、メタ塗りつぶしの塗りつぶしである。次のステップ１０４０では、アクティブ塗りつぶしを使用してレンダリングすべき画素の数が判定される。アクティブ塗りつぶしを使用してレンダリングすべき画素の数は、レンダリングモジュール６６０がレンダリングすることを要求する画素の数と、アクティブ塗りつぶしにおいて残留している画素の数のうちで小さいほうの数として判定される。アクティブ塗りつぶしにおいて残留している画素の数は、アクティブ塗りつぶしの最大ｘ位置から現在のレンダラｘ位置を減算した値に基づいて判定される。
【００７５】
レンダリングされるべき画素の数が判定されたならば、方法１０００は、ステップ１０５０へ進む。ステップ１０５０では、要求された画素ランがレンダリングされる。画素データを生成するために、ディスパッチャ６８０は、アクティブ塗りつぶしの塗りつぶし型に従って、アクティブ塗りつぶしをネイティブレンダリング機能へ送信する。また、ステップ１０５０では、現在のレンダリングｘ位置及びレンダリングされるべき画素の数が更新される。方法１０００は、次のステップ１０６０に続く。ステップ１０６０において、レンダリングされるべき画素が他にまだ存在している場合、方法１０００は、ステップ１０７０へ進む。そうでない場合には、方法１０００は終了する。ステップ１０７０で、プロセッサ４０５は、メタ塗りつぶしにおける次の塗りつぶしを検索する。ステップ１０７０で検索された塗りつぶしは、アクティブ塗りつぶしになる。ステップ１０７０に続いて、方法１０００は、ステップ１０４０へ進む。
【００７６】
一例として、図８Ａは、１つの平行四辺形の形態をとるコンパイルドオブジェクト８２０を含むページ８３０を示す。コンパイルドオブジェクト８２０は、コンパイルドオブジェクト８２０の一部を閉塞する円オブジェクト８１０を有する。円オブジェクト８１０は、白色フラット塗りつぶしを含む。コンパイルドオブジェクト８２０は、４つの塗りつぶし８０７、８０９、８１１及び８１３を有する。これらの塗りつぶしは、図８Ｂに示されるように、１つのメタ塗りつぶし８３５の中に含まれていてもよい。
【００７７】
メタ塗りつぶし８３５は、指定された走査線（すなわち、３００）に関して、メタ塗りつぶし８３５の中の第１の塗りつぶし８０７の開始場所（すなわち、画素１００）を指示するトラッキングポイント変数８４４を含むヘッダ８３７を含む。ヘッダ８３７は、トラッキングポイントＤＸ８６５を含む。ヘッダ８３７は、次の塗りつぶし８０９を記述する塗りつぶし構造８３８を指示するポインタを更に含む。
【００７８】
塗りつぶし構造８３８は、ヘッダ８３９を含む。ヘッダ８３９は、塗りつぶし型変数８４６を使用して、塗りつぶし型を説明する。塗りつぶし型変数８４６は、塗りつぶし８０７がパターン塗りつぶしであることを示す。ヘッダ８３９は、塗りつぶし８０７の画素ランの長さを表すサイズ変数８４７を更に含む。塗りつぶし８０７は、２０画素にわたる。塗りつぶし構造８３８は、ストライプパターン塗りつぶしデータ８６１を更に含む。最後に、ヘッダ８３９は、次の塗りつぶし８０９を説明する次の塗りつぶし構造８４１を指示するポインタ８４８を含む。
【００７９】
塗りつぶし構造８４１は、ヘッダ８４３を含む。ヘッダ８４３は、塗りつぶし型変数８４９を使用して、塗りつぶし型を説明する。塗りつぶし型変数８４９は、塗りつぶし８０９がパターン塗りつぶしであることを示す。ヘッダ８４１は、塗りつぶし８０９の画素ランの長さが１００画素であることを示すサイズ変数８５０を更に含む。塗りつぶし構造８４１は、クロスハッチパターン塗りつぶしデータ８６２を更に含む。最後に、ヘッダ８４３は、次の塗りつぶし８１１を説明する次の塗りつぶし構造８４５を指示するポインタ８５１を含む。
【００８０】
塗りつぶし構造８４５は、ヘッダ８５２を含む。ヘッダ８５２は、塗りつぶし型変数８５３を使用して、塗りつぶし型を説明する。塗りつぶし型変数８５３は、塗りつぶし８１１がパターン塗りつぶしであることを示す。ヘッダ８５２は、塗りつぶし８１１の画素ランの長さを表すサイズ変数８５４を更に含む。サイズ変数８５４により示されるように、塗りつぶし８１１は、１５０画素に及ぶ。塗りつぶし構造８４５は、ドットパターン塗りつぶしデータ８６３を更に含む。最後に、ヘッダ８５２は、次の塗りつぶし８１３を説明する次の塗りつぶし構造８５６を指示するポインタ８５５を含む。
【００８１】
塗りつぶし構造８５６は、ヘッダ８５７を含む。ヘッダ８５７は、塗りつぶし型変数８５８を使用して、塗りつぶし型を説明する。塗りつぶし型変数８５８は、塗りつぶし８１３がフラット塗りつぶしであることを示す。ヘッダ８５７は、塗りつぶし８１３の画素ランの長さを表すサイズ変数８５９を更に含む。サイズ変数８５９により示されるように、塗りつぶし８１３は、４０画素にわたる。塗りつぶし構造８５６は、フラット塗りつぶしデータ８６４を更に含む。最後に、ヘッダ８５７は、次の塗りつぶし構造を指示するポインタ８６０を含む。しかし、図８Ａ及び図８Ｂの例においては、他に塗りつぶしは存在しないため、ポインタ８６０の値はヌルである。
【００８２】
円オブジェクト８１０は、メタ塗りつぶし８３５より高いZ-オーダー（Z-order）を有し、従って、コンパイルドオブジェクト８２０の一部を閉塞している。レンダリングモジュール６６０の現在のレンダリング位置が円オブジェクト８１０上の点８０５と交差するのに応答して、点８０６に続く第１の画素と関連する塗りつぶしが判定されなければならない。点８０５において、ｙ位置は３００であり（すなわち、現在の走査線が３００である）、ｘ位置は２６５である。コンパイラ６７０は、コンパイルドオブジェクト８２０の塗りつぶしがメタ塗りつぶし８３５であると判定し、方法１０００のステップ１０１０の通りに、デコンパイリングのために、塗りつぶしをディスパッチャ６８０へ送信する。ディスパッチャ６８０は、方法１０００のステップ１０１５の通りに、メタ塗りつぶし８３５のトラッキングポイントを、現在の走査線（すなわち、走査線３００）におけるコンパイルドオブジェクト８２０のトラッキングポイント８１５と一致するように更新する。
【００８３】
ディスパッチャ６８０は、メタ塗りつぶし８３５のトラッキングポイント変数８４４の現在のｙ位置と、レンダリングされるべき現在の走査線（すなわち、走査線３００）のｙ位置との距離を判定することにより、現在の走査線のトラッキングポイント変数８４４を更新する。次に、ディスパッチャ６８０は、判定された距離（０になる場合も有る）をトラッキングポイントＤＸ８６５と乗算し、メタ塗りつぶし８３５のトラッキングポイント変数８４４の新たなｘ位置を判定する。メタ塗りつぶし８３５のトラッキングポイント変数８４４の新たなｙ位置は、現在の走査線の現在のｙ位置と一致するように更新される。図８Ａ及び図８Ｂの例では、先に説明したように、現在の走査線のトラッキングポイント８１５のトラッキングポイント変数８４４は、（１００，３００）である。
【００８４】
ディスパッチャ６８０は、方法１０００のステップ１０３０の通りに、現在「アクティブ」である塗りつぶしを判定するために、トラッキングポイント８１５を示す判定されたトラッキングポイント変数８４４を使用してもよい。現在アクティブである塗りつぶしは、点８０５に続く第１の画素についてレンダリングされるべき塗りつぶしである。ディスパッチャ６８０は、点８０５におけるｘ位置と、トラッキングポイント８１５のｘ位置との距離を判定する。図８Ａの例では、点８０５において、ｘ位置は、トラッキングポイント８１５から１６５画素（すなわち、２６５−１００）の距離にある。次に、ディスパッチャ６８０は、トラッキングポイント８１５から１６５番目の画素と関連する塗りつぶしを判定するために、メタ塗りつぶし８３５と関連する連係塗りつぶし構造８３８、８４１、８４５及び８５６のリストを検討する。ディスパッチャ６８０は、現在の塗りつぶしが１６５番目の画素に及ぶまで、連係塗りつぶしの個別の画素ランの長さを累積することにより、１６５番目の画素と関連する塗りつぶしを判定する。コンパイルドオブジェクト８２０の場合、先に説明したように、第１の塗りつぶし８０７は、２０画素にわたり、第２の塗りつぶし８０９は、１００画素にわたり、第３の塗りつぶし８１１は、１５０画素にわたり、最後の塗りつぶし８１３は、４０画素にわたる。図８Ａ及び図８Ｂの例においては、第３の塗りつぶし８１１がトラッキングポイント８１５から１６５番目の画素を含む。従って、第３の塗りつぶし８１１が、現在アクティブである塗りつぶしと呼ばれることになる。図８Ａからわかるように、第３の塗りつぶし８１１は、トラッキングポイント８１５から１２０番目の画素で始まる。図８ＡにおいてＡｘとマークされた線は、１２０画素分の長さを有する。ページの境界８３０を参照すると、１２０番目の画素は、現在の走査線（すなわち、走査線３００）上の画素番号２２０に相当する。レンダリングモジュール６６０の現在のレンダリング位置は、画素番号２６５であるので、図８ＡにおいてＬｘにより示されるように、ディスパッチャ６８０は、第３の塗りつぶし８１１のうちの４５画素（すなわち、２６５−２２０）が経過したと判定してもよい。図８Ａからわかるように、Ｆｘは、現在アクティブである塗りつぶし８１１に関して、レンダリングされるべき画素の数を表す。ディスパッチャ６８０は、方法１０００のステップ１０４０の通りに、現在アクティブである塗りつぶし８１１に関して、レンダリングされるべき画素の数は１０５画素（すなわち、１５０−４５）であると判定する。
【００８５】
次に、ディスパッチャ６８０は、方法１０００のステップ１０５０の通りに、ネイティブレンダリング機能を使用して、Ｆｘにより表される第３の塗りつぶし８１１のうちの１０５画素をレンダリングすることを、レンダリングモジュール６６０に要求する。レンダリングモジュール６６０が、現在アクティブである塗りつぶし８１１に従って、１０５画素のレンダリングを終了すると、レンダリングされるべき現在の走査線の画素ランが他に存在するとディスパッチャ６８０が判定した場合、ディスパッチャ６８０は、方法１０００のステップ１０７０の通りに、次のアクティブ塗りつぶしを判定する。
【００８６】
先に説明したように、コンパイルドオブジェクトを形成するために、複数のグラフィカルオブジェクトを組み合わせ、それにより、冗長稜線を除去してもよい。走査線ごとに分類、追跡される必要がある稜線とは異なり、メタ塗りつぶしの属性は、高レベルで、一度判定されるだけでよいので、多数の稜線を分類、追跡しなければならない従来のレンダリング方法と比べて、コンパイルドオブジェクトのレンダリングは、はるかに効率がよい。
【００８７】
ステップ９８３及び／又は９９０で、コンパイラ６７０は、塗りつぶし型の異なるグラフィカルオブジェクトを組み合わせてもよい。コンパイラ６７０は、そのようなオブジェクトの稜線を組み合わせ、オブジェクトと関連する塗りつぶしを、同一のオブジェクトに属する別個のエンティティとして扱う。従って、ビットマップを組み合わせる場合、その他に画像操作又はコピーを実行する必要はない。オブジェクトと関連する塗りつぶしは、別個に処理され、格納されてもよいが、コンパイラ６７０により、一体に連係される。例えば、図１６は、図６のグラフィックスデバイスインタフェース６２０により生成された２つのビットマップ１６３０及び１６４０を連係するメタ塗りつぶし１６６０を示す。図１６の例では、グラフィックスアプリケーション６１０のようなグラフィックスアプリケーションにより作成された元のビットマップ１６２０が、グラフィックスデバイスインタフェース６２０により、２つの別個のビットマップ１６３０及び１６４０として送信される。コンパイラ６７０は、ビットマップ１６３０及び１６４０は互いに並列して位置することを認識し、そこで、２つのビットマップ１６３０及び１６４０からメタ塗りつぶし１６６０を生成する。これとは対照的に、従来のレンダリング方法は、一方のビットマップ（例えば、ビットマップ１６３０）のデータを他方のビットマップ１６４０にコピーすることにより、ビットマップ１６３０及び１６４０を組み合わせるため、効率が悪い。
【００８８】
また、先に説明したように、従来のレンダリング方法は、非線形勾配塗りつぶし５１０のような非線形勾配塗りつぶしから、多数の勾配塗りつぶしを生成する。しかし、先に説明したように、勾配塗りつぶし５１０は、多数の塗りつぶし要素を伴って、単一のコンパイルドオブジェクトとして処理されてもよい。そのようにすることにより、メタ塗りつぶしにおいて関連する線形勾配を保持しつつ、冗長稜線を除去できる。単純なフラット塗りつぶしを組み合わせる場合、コンパイラ６７０が同一の色のオブジェクトの組み合わせのみに限定されることはない。コンパイラ６７０は、色の異なるオブジェクトであっても、更には、塗りつぶし型の異なるオブジェクトであっても、組み合わせることができる。それは、塗りつぶしが再び連係されるからである。従って、オブジェクトの稜線が１つに組み合わせられる一方で、必要な全ての塗りつぶし情報は依然としてレンダリングモジュール６６０に提示される。
【００８９】
図１３は、６つの基本オブジェクト１３１０、１３２０、１３３０、１３４０、１３５０及び１３６０を示す。従来のレンダリングシステム３３０は、オブジェクト１３１０〜１３６０の各々を２つの稜線（例えば、オブジェクト１３１０の場合、稜線１３１１及び１３１２）として処理する。各稜線１３１１は、関連するレベルデータ１３１３及び塗りつぶしデータ１３１４を有する。これに対し、図１４は、オブジェクト１３１０〜１３６０から形成されたコンパイルドオブジェクト１４１０を示す。図１４からわかるように、コンパイルドオブジェクトは、関連するメタ塗りつぶし１４１５を有する。レンダリングモジュール６６０は、コンパイルドオブジェクト１４１０を単一のオブジェクトとして処理し、従って、コンパイルドオブジェクト１４１０のアウトライン１４１３を記述する稜線１４１１及び１４１２の知識を有するのみである。
【００９０】
基本オブジェクト１３１０〜１３６０をレンダリングする時に、モジュール３６０のような従来の稜線ベースレンダリングモジュールは、走査線ごとに、各オブジェクトの各々の稜線（例えば、稜線１３１１）を更新する。個々の走査線ごとに、レンダリングモジュール３６０が稜線１３１１のような左側の稜線に遭遇すると、レベルデータ１３０３がロードされなければならず、また、塗りつぶしデータ１３１４から、画素ランが計算されなければならない。これとは対照的に、メタ塗りつぶし１４１５のようなメタ塗りつぶしを符号化し、復号することにより、レンダリングモジュール６６０は、２つの稜線を処理するだけでよく、単一のレベルをロードするだけでよい。例えば、レンダリングモジュール６６０は、オブジェクト１３１０〜１３６０の各々の稜線を個別に追跡する必要がない。それは、全ての稜線（例えば、稜線１３１１及び１３１２）が平行であるからである。そのため、塗りつぶしデータは、常に、メタ塗りつぶし１４１５の中の第１の塗りつぶし１４１７に関連して判定され、その結果、レンダリングモジュールにより要求される労力の量は大幅に減少する。ディスパッチャ６８０は、画素データを効率よく生成できるであろう。メタ塗りつぶし１４１５のようなメタ塗りつぶしを使用するとき、走査線ごとに要求される唯一の更新は、トラッキングポイント（例えば、１１２１）の更新である。
【００９１】
グラフィックスレンダリングシステム３３０のような従来のグラフィックスレンダリングシステムの場合、ＲＧＢからＣＭＹＫへの色変換を実行する。そこで、ＣＭＹＫ色変換線形勾配塗りつぶしを表現するための多くの方法が知られている。１つの方法は、ＲＧＢ勾配塗りつぶしをＲＧＢ空間におけるビットマップに変換し、次に、各画素色をＣＭＹＫに変換して、色修正ビットマップを生成する。別の方法は、勾配塗りつぶしに沿ってＲＧＢ色空間における多数の点をサンプリングし、それらの点を色変換して、色変換勾配塗りつぶしに近似する多数の小さな線形ＣＭＹＫ勾配塗りつぶしを生成する。更に別の方法は、ＲＧＢ勾配塗りつぶしをサンプリングし、元の勾配塗りつぶしを表現する複数のＣＭＹＫフラット塗りつぶしを生成する。
【００９２】
線形勾配塗りつぶしをＣＭＹＫビットマップとして表現することは、元のＲＧＢ勾配塗りつぶし記述と比較して、非常に不効率である。更に、ＲＧＢ勾配塗りつぶし（RGB gradient fill ）を、多数の小さなＣＭＹＫ勾配塗りつぶし（CMYK gradient fills ）又はＣＭＹＫフラット塗りつぶし（CMYK flat fills ）に分解することは、隣接する勾配塗りつぶしの間に数多くの稜線が生成され、従って、レンダリングモジュール３６０のような従来のレンダリングモジュールの動作速度が劇的に遅くなるという欠点を有する。しかし、多数のＣＭＹＫ勾配塗りつぶし又はフラット塗りつぶしは、先に説明したメタ塗りつぶし１４１５のような単一のメタ塗りつぶしとして表現されてもよい。そのようなメタ塗りつぶし１４１５を使用することで、色空間変換中にオブジェクトに導入された追加稜線は除去される。
【００９３】
オブジェクト１４１３のようなコンパイルドオブジェクトとして組み合わされるオブジェクトの数が多くなるほど、コンパイルドオブジェクトの画素ラン（pixel runs ）は長くなる。特に、先行する走査線から、キャッシュされた画素ランを再利用することが可能である場合、多数のコンパイルドオブジェクトは、より長い画素ランから大きな利益を受ける。例えば、同一の色のフラット塗りつぶしを１つのコンパイルドオブジェクトとして組み合わせると、オブジェクトの画素ランは、より大きくなり、キャッシュの再利用は改善される。更に、レンダリングモジュールの中には、そのレンダリングモジュールがレンダリングできる、１ページ当たりのオブジェクトの量が限られているものもあるため、先に説明したように、１つのコンパイルドオブジェクト及び関連するメタ塗りつぶしを生成することにより、ソフトウェアフォールバックジョブ（すなわち、ターゲットデバイスでレンダリングを実行するには、現在のページが余りにも複雑であるために、完全にソフトウェアのみによりレンダリングされるジョブ）を形成する必要なく、ハードウェアによるページのレンダリングが可能になる。
【００９４】
上述の好ましい方法は、特定の制御フローを含む。本発明の趣旨の範囲から逸脱せずに、異なる制御フローを使用する好ましい方法の他の変形が数多く存在する。更に、好ましい方法のステップのうちの１つ以上は、順次実行されるのではなく、並行して実行されてもよい。
【００９５】
以上、本発明のいくつかの実施形態のみを説明した。本発明の趣旨の範囲内から逸脱せずに、それらの実施形態に対して変形及び／又は変更を実施することは可能である。上述の実施形態は単なる例示であり、限定的な意味を持たない。
【図面の簡単な説明】
【００９６】
【図１】従来のソフトウェアアプリケーションと、グラフィックスデバイスインタフェースレイヤと、グラフィックスレンダリングシステムと、ターゲットデバイスとの従来の関係を示す図である。
【図２Ａ】放射勾配塗りつぶしの一例を示す図である。
【図２Ｂ】非線形勾配塗りつぶしの一例を示す図である。
【図２Ｃ】線形勾配塗りつぶしの一例を示す図である。
【図３】従来のグラフィックスレンダリングシステムを示す図である。
【図４】説明される構成を実施できる汎用コンピュータの概略ブロック線図である。
【図５Ａ】非線形勾配塗りつぶしを示す図である。
【図５Ｂ】図５Ａの非線形勾配塗りつぶしから生成される２つの線形勾配塗りつぶしを示す図である。
【図５Ｃ】複数の線形勾配塗りつぶしを示す図である。
【図６】２段階稜線ベースグラフィックスレンダリングシステムを示す図である。
【図７Ａ】元の稜線ベースオブジェクトを示す図である。
【図７Ｂ】従来の方式により、塗りつぶし、稜線及びレベルとして格納された図７Ａのオブジェクトを示す図である。
【図７Ｃ】塗りつぶし、稜線及びレベルにより表現されるコンパイルドオブジェクトとして格納された図７Ａのオブジェクトを示す図である。
【図８Ａ】コンパイルドオブジェクトの一部を閉塞する円を有するコンパイルドオブジェクトを示す図である。
【図８Ｂ】図８Ａのコンパイルドオブジェクトの塗りつぶしを説明するメタ塗りつぶしを示す図である。
【図９】複数のオブジェクトを組み合わせて、コンパイルドオブジェクトを生成する方法を示す図である。
【図１０】コンパイルドオブジェクトをレンダリングする方法を示す流れ図である。
【図１１】メタ塗りつぶしを示す概略図である。
【図１２】関連するメタ塗りつぶしと共にコンパイルされたオブジェクトの一例を示す図である。
【図１３】関連する稜線データ及びレベルデータと共に６つの基本オブジェクトを示す図である。
【図１４】図１３のオブジェクト及び関連するメタ塗りつぶしから形成されたコンパイルドオブジェクトを示す図である。
【図１５Ａ】組み合わせ可能なオブジェクトのいくつかの例を示す図である。
【図１５Ｂ】組み合わせ可能なオブジェクトのいくつかの例を示す図である。
【図１５Ｃ】組み合わせ可能なオブジェクトのいくつかの例を示す図である。
【図１５Ｄ】組み合わせ可能なオブジェクトのいくつかの例を示す図である。
【図１５Ｅ】組み合わせ可能なオブジェクトのいくつかの例を示す図である。
【図１５Ｆ】組み合わせ不可能なオブジェクトのいくつかの例を示す図である。
【図１５Ｇ】組み合わせ不可能なオブジェクトのいくつかの例を示す図である。
【図１６】２つのビットマップをリンクするメタ塗りつぶしの一例を示す図である。
【図１】
2005267639.tif 000003
【図２Ａ】
2005267639.tif 000004
【図２Ｂ】
2005267639.tif 000005
【図２Ｃ】
2005267639.tif 000006
【図３】
2005267639.tif 000007
【図４】
2005267639.tif 000008
【図５Ａ】
2005267639.tif 000009
【図５Ｂ】
2005267639.tif 000010
【図５Ｃ】
2005267639.tif 000011
【図６】
2005267639.tif 000012
【図７Ａ】
2005267639.tif 000013
【図７Ｂ】
2005267639.tif 000014
【図７Ｃ】
2005267639.tif 000015
【図８Ａ】
2005267639.tif 000016
【図８Ｂ】
2005267639.tif 000017
【図９】
2005267639.tif 000018
【図１０】
2005267639.tif 000019
【図１１】
2005267639.tif 000020
【図１２】
2005267639.tif 000021
【図１３】
2005267639.tif 000022
【図１４】
2005267639.tif 000023
【図１５Ａ】
2005267639.tif 000024
【図１５Ｂ】
2005267639.tif 000025
【図１５Ｃ】
2005267639.tif 000026
【図１５Ｄ】
2005267639.tif 000027
【図１５Ｅ】
2005267639.tif 000028
【図１５Ｆ】
2005267639.tif 000029
【図１５Ｇ】
2005267639.tif 000030
【図１６】
2005267639.tif 000031
【外国語明細書】
1.Title of Invention
A METHOD OF RENDERING GRAPHICAL OBJECTS
2.Field of the Invention
The present invention relates generally to image processing and, in particular, to a method of rendering a plurality of graphical objects.  The present invention also relates to a method and apparatus for rendering a plurality of graphical objects, and to a computer program product including a computer readable medium having recorded thereon a computer program for rendering a plurality of graphical objects.
3.Background
Conventional software applications, such as word processors, create page-based documents where each page may contain one or more graphical objects (ie., text, lines, fill regions and/or image data).  When representing such documents on a display device or a printing device, a software application typically sends commands to the device.  These commands are typically defined by graphical interface services associated with a native operating system which is executing the software application.  One such operating system is Windows?.  The graphics interface services of the Windows? operating system are typically referred to as a graphics device interface (GDI) layer.  The GDI layer may be implemented as an application programming interface (API) being executed by the operating system and providing a rich set of graphics features to software applications being executed by the operating system.  
A graphics rendering system typically renders graphical objects received from the GDI layer of an operating system, generating pixels.  Rendering is the process by which graphical objects received from the GDI layer are converted to pixels by a graphics rendering system.  The pixels generated by the graphics rendering system are then sent to an output device for display and/or printing.  
Fig. 1 shows the relationship between a conventional software application 110, a graphics device interface layer 120, a graphics rendering system 130 and a target device 140.  The application 110 passes each page of a document as a series of commands.  For each page to be rendered, the series of commands are defined in terms of graphic interface services which describe the graphical objects of the page.  The GDI layer 120 mediates between the application program 110 and the target device 140.  The GDI layer 120 enables the graphics rendering system 130 to support a much smaller set of functionality than the Windows? operating system can handle.  The GDI layer 120 also provides graphical objects to the graphics rendering system 130 in a format that the GDI layer 120 determines is the most efficient for the graphics rendering system 130 and at a resolution of the target device 140.  The graphics rendering system 130 then renders the graphical objects received from the GDI layer 120, generating pixels.  The pixels generated by the graphics rendering system 120 are then sent to the target device 140.
There are a wide range of graphics software applications.  Many of these graphics software applications are capable of producing complex graphical objects.  These objects are usually specific to a particular graphics software application.  For example, one well known graphics software application referred to as Corel DrawTM can create a complex object know as a 'fountain fill'.  A 'fill' is used to describe pixel data that a graphical object is painted (ie., filled) with.  For example, a red square has a red flat coloured fill.  A fountain fill is a type of 'gradient fill' which describes the fill of an object where two or more colours of the object flow into each other smoothly.  Gradient fills come in many types (eg., linear, conical, radial and non-linear).  An object 210 filled with a radial gradient fill is shown in Fig 2A.  A gradient fill transition usually consists of one colour flowing into another.  However, more complex gradient fills may have many transitions between many different colours.  Fig. 2B shows an example of an object 220 filled with a gradient fill that has many transitions.  
The method used by a particular graphics software application for filling an object with a linear gradient fill is dependent on the particular graphics software application.  However, one known method of filling an object with a linear gradient fill comprises the step of specifying a start colour and an end colour at each end of the bounding box of a graphical object being filled and interpolating between the start and end colour.  
Complex graphical objects such as the objects 210 and 220 are not typically able to be directly rendered by a printer or display driver.  Therefore, a GDI layer typically passes gradient fills to a graphics rendering system as a number of flat filled adjacent objects in the form of parallelograms.  These flat filled adjacent parallelograms enable the graphics rendering system to render a complex graphical object without the need to support any application specific graphics types.  For renderers which use a Painters Algorithm method of rendering, flat filled parallelograms may be rendered to a frame store.  However, since both linear and non-linear gradient fills are typically passed by the GDI layer as flat filled parallelograms, the width of any two adjacent parallelograms is not typically consistent.  As a result, colour change between consecutive sets of these parallelograms is not always linear.
In some graphics rendering systems, the rendering process is a two-stage process.  In such rendering systems, graphical objects of a page to be rendered are firstly converted into an intermediate format before the rendering process begins.  This intermediate format is known as a 'display list'.  In one such graphics rendering system, the first stage of the rendering process converts each graphical object of the page received from an associated operating system into an intermediate edge-based object.  For example, Fig. 3 shows a conventional graphics rendering system 330 that converts each received graphical object into an intermediate edge-based object.  In the example of Fig. 3, a linear gradient fill 370 corresponding to a complex graphical object, created by a graphics application 310 is passed to the graphics rendering system 330 from the graphics device interface 320, as a number of flat coloured rectangles (eg., the flat coloured rectangle 380).  A display list creation module 340 of the graphics rendering system 330, converts each of the flat coloured rectangles 380 into two edges, a level, and fill data, which are stored in databases (eg., 381, 382 and 383, respectively).  The edges describe the area in which each flat coloured rectangle 380 is filled.  The fill data provides the colour/opacity of the pixels inside the edges of the flat coloured rectangle 380.  The fill data may be a flat colour, a bitmap, an equation or pattern that describes pixel data at a specific position within the flat coloured rectangle 380.  The level contains important rendering information such as a z-order for the coloured rectangle 380, the raster operation to be applied to the fill data and whether an associated edge is a clipping edge or a filling edge.
Before the graphics rendering system 330 can render one of the flat coloured rectangles 380, each rectangle must be sorted, such that all edges of a particular rectangle are sorted in ascending y, then ascending x order.  The y and x coordinates correspond respectively to the scan lines and pixel locations on each scan line in a rasterized rendering system.  The graphics rendering system generates a display list 350 of edges and their associated fill priority (z-order), along with other information such as if an edge is a clipping edge or a filling edge.
A display list 350 is sometimes referred to as a job.  The job comprises all of the information needed by a rendering module 360 of the graphics rendering system 330 to render the page.  The rendering of the page by the rendering module 360 is the second stage of the rendering process.  
The rendering module 360 parses the job and generates pixels for a downstream device such a printer, for each scanline down the page.  For each scanline, as the rendering module 360 encounters the left edge of a coloured rectangle (eg., the rectangle 380), the rendering module 360 loads the level associated with the rectangle into an intermediate buffer.  The level associated with the rectangle is now said to be active.  The level associated with the rectangle is deactivated when the rendering module 360 encounters the right edge of the rectangle.  
The rendering module 360 allows for different types of activation rules for edges, which will be explained later in this document.  The pixel span between each set of edges on a scanline is rendered according to these rules.  When the rendering module 360 encounters an edge, the rendering module 360 determines a top most (ie., greatest z-order position) currently active level and renders the pixels according to the fill data of the top most currently active level.  If the object (eg., a flat filled rectangle) corresponding to the top most level is transparent, then compositing of lower z-order levels is used to calculate the resulting pixel data.  Every edge the rendering module 360 encounters has to be updated to a new position on a next scanline.  In addition, since edges may cross one another, edges must also be sorted to ensure that the edges remain in ascending x order.  The rendering process continues on a scanline per scanline basis until all the pixels on the page are rendered.
As described above, complex objects are typically broken down into simpler objects, such as flat filled rectangles, by the graphics device interface 320.  Each of these simpler objects has to be converted to the intermediate form separately, which takes considerable time.  When rendering each individual flat fill object, each of the edges of the object need to be sorted and each edge updated for every scanline, which is also a time consuming process for the rendering module 360.  So, for a complex object that has been broken down into hundreds of simpler objects, converting each object into an intermediate edge based format and rendering the complex object using an edge based rendering module is highly inefficient.
As an example, the horizontal linear gradient fill 230 shown in Fig 2C may be broken down into two hundred and fifty six (256) flat fill rectangles by the graphics device interface 320 before being passed to the graphics rendering system 330.  In the worst case of the gradient fill 230 proceeding left to right or right to left, all two hundred and fifty-six (256) flat fills become active on a scanline, equating to five hundred and twelve (512) edges per scanline.  Hence for an edge-based rendering system, such a method of rendering is considerably inefficient, due to the large amount of edge sorting and tracking that needs to be performed per scanline.  In addition, each flat fill must be stored into an intermediate object-graphics format, accessed for each fill-path for each scanline and then all of the edges sorted before rendering can begin. 
The above rendering method requires large amounts of memory accesses and can also consume large amounts of fill resources when the number of flat fills to be processed is in the order of thousands.  Such numbers of flat fills can occur frequently when printing pages larger than A3 at high-resolutions.
One way to increase the rendering performance of the edge based rendering module 360, when rendering the gradient fill 230, is to reduce the number of edge updates and the amount of edge sorting that needs to be carried out.  One known method of reducing edge updates and sorting is to remove redundant edges where possible by compiling graphical objects into a larger single graphic object or into a more complex object that a rendering module can handle.  There are a number of known methods for compiling graphical objects into a larger single graphical object.  For example, two separate adjacent bitmaps may be stitched together to form one large bitmap, two contiguous flat fills with the same colour may be combined to produce one larger single flat fill, and contiguous flat fill primitives representing a linear gradient fill may be combined into a complex linear gradient fill of a type that can be rendered by a graphics rendering system.  However, these known rendering methods of rendering all have disadvantages and limitations.
For example, known rendering methods that attempt to combine contiguous objects are limited to specified fill types available to a particular rendering module.  Therefore, the only objects that can be combined are those that have the exact same fill type as each other.  These types of objects do not occur often since a GDI layer such as the GDI 320 has no need to break these objects down in the first place.
For those methods that combine bitmaps, whole image fill data has to be copied to combine two different bitmaps into one bitmap.  Copying image fill data can be a slow process, especially when a number of bitmaps are involved as a large number of memory allocations and a large amount of image data copying needs to be performed.
Those methods of rendering that combine flat fill primitives into complex equivalents are limited to outputting fills that are supported by a particular rendering module.  One fill that is likely to be supported by a particular rendering module is a linear gradient fill, which is usually represented by two or three points and corresponding colour values at those points.  
As described earlier, it is not atypical for the GDI 320 to pass a gradient fill as a number of flat filled parallelograms, with inconsistent parallelogram widths and non-constant colour changes.  For gradient fills that are not linear, (eg., a non-linear gradient fill 510 as shown in Fig. 5A), known rendering methods attempt to combine the individual flat fill parallelograms into equivalent linear gradient components.  Known rendering methods that compile non-linear gradient fill objects into linear gradient fills ideally produce two linear gradient fills.  Fig. 5B shows two linear gradient fills 520 and 525, produced from the non-linear gradient fill 510 of Fig. 5A.  Due to non constant colour changes and inconsistent parallelogram widths produced by the GDI 320 given the non-linear gradient fill 510, the known method of compiling gradient fills does not produce the ideal results of Fig. 5B since such a method cannot deal with inconsistencies within the gradient fill 510.  
Conventional rendering methods often produce a large number of linear gradient fills  530 - 537, as shown in Fig 5C.  Producing such a large number of linear gradient fills can be less efficient than an original flat fill representation, ultimately slowing a rendering module down.  The rendering module is slowed down because linear gradient fill pixel data is more difficult to calculate than that of a flat fill and since only a minimal number of edges are typically removed, the net effect is actually a slow down in rendering speed.  Flat fills (eg., the flat fill rectangle 380) representing a gradient fill that arrive from the GDI 320 are not always consistent and do not always have reasonable linear colour change limits.  Conventional methods of rendering are therefore very limited in handling flat fills in an efficient manner.  Further, conventional rendering methods lack the ability to fully optimise graphic primitives because an associated rendering module lacks the available functionality.
A further disadvantage of rendering linear gradient fills occurs due to the fact that printers use subtractive primary colours cyan, magenta and yellow (CMY) and also black (K) to produce colour images on a page.  As a result, it is necessary to convert a linear gradient fill stored in the RGB colour space to the CMYK colour space.  The conversion of a linear gradient fill from the RGB colour space to the CMYK colour space can be done within a host computer or at a target device.  However, a linear gradient fill that is described in terms of two or three points, each point having a corresponding colour value in the RGB colour space, can not be colour converted by simply converting the colour at each point since original colour data, passed by a GDI, does not map linearly  into the colour converted colour space.  That is, there is no linear relationship between the RGB colour space and the CMYK colour space.  Conventional methods of colour converting a linear gradient fill, determine RGB values of pixel data for each pixel within the fill.  Each of the pixels within the linear gradient fill are then converted into an equivalent CMYK colour value.  The colour converted linear gradient fill is then added to a display list as a bitmap.  Therefore, storing a linear gradient fill in the RGB colour space is very inefficient.
Thus, a need clearly exists for a more efficient method of rendering graphical objects.
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 one aspect of the present invention there is provided a method of rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order, and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said method comprising the steps of:
combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more fill data structures representing the fills associated with said graphical objects; and 
rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.  
According to another aspect of the present invention there is provided a compound fill for rendering a graphical object, said graphical object comprising a predetermined object outline and said compound fill, the predetermined object outline defining an area in which said graphical object is filled, wherein said compound fill is configured as a data structure containing a plurality of fills, said fills defining a manner in which said graphic object is to be filled upon rendering.
According to still another aspect of the present invention there is provided an apparatus for rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order,  and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said apparatus comprising:
combining means for combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more  fill data structures representing the fills associated with said graphical objects; and 
rendering means for rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.
According to still another aspect of the present invention there is provided a computer program for rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order,  and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said program comprising:
code for combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more fill data structures representing the fills associated with said graphical objects; and 
code for rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.
According to still 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 rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order,  and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said program comprising:
code for combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more fill data structures representing the fills associated with said graphical objects; and 
code for rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.
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.
It is to be noted that the discussions contained in the "Background" section and that above relating to prior art arrangements relate to discussions of documents or devices which form public knowledge through their respective publication and/or use.  Such should not be interpreted as a representation by the present inventor(s) or patent applicant that such documents or devices in any way form part of the common general knowledge in the art.  
A method 900 (see Fig. 9) of combining a plurality of objects is described below with reference to Fig. 1 to 16.  The method 900 efficiently combines a set of contiguous graphical objects to generate a high level compiled object representing the combination of the contiguous objects.  The compiled object may also be referred to as a "grouped" object.  The method 900 may be used to combine such contiguous objects even if the objects have different fill types.  The method 900 outputs the compiled object to a display list. 
The compiled object has an associated meta-fill.  The meta-fill is a compound fill, which may be used to describe a collection of fills associated with the compiled object.  As will be described in detail below, the meta-fill comprises a head structure to define information about the meta-fill.  The head structure is followed by a linked list of fill structures that describe the fills of the compiled object.  A plurality of the fills of the compiled object may be combined into one simple compound or complex fill in order to minimise size of the linked list.
A meta-fill may be used to combine a set of simple primitive objects (primitives) lying side by side to form a complex primitive object, such that only two edges are required to represent the set of primitives. The meta-fill reduces rendering time by re-uniting complex drawing objects, such as non-linear blends the graphics interface has represented by numerous flat fills.  For example, a meta-fill similar to the non-linear gradient fill 510 may be formed from the linear gradient fills 530-537 of Fig. 5C.  Such a meta- fill is a great improvement over the linear gradient files 530-537 of Fig. 5C.
Meta-fills do not alter information provided by a GDI such as the GDI 320, for example.  However, a meta-fill will remove occluded parts of an object when two objects overlap.  Substantially, no information is lost in the conversion of fills to a meta-fill.  All of the information of one or more primitive fills used to form a meta-fill is retained to ensure that drawing output remains consistent and is not affected when the primitive fills are combined into the meta-fill.  In contrast, conventional methods affect color information such that output is never guaranteed to reflect input.  Meta-fills also reduce edge overhead.
For rendering systems that produce PDLs, a meta-fill reduces the size of a PDL required to represent primitive objects. Reducing the size of a PDL improves processing where transmission of the PDL is required.
A meta-fill may be formed using flat fills, linear gradient fills, and bitmaps.  In contrast, conventional rendering systems typically only recognise flat fills representing color blends.
The compiled object may be efficiently rendered using the associated meta-fill by decoding the meta-fill in real time.  A method 1000 (see Fig. 10) of rendering a compiled object is also described with reference to Fig. 1 to 16.  
The methods described herein may be implemented using a general-purpose computer system 400, such as that shown in Fig. 4 wherein the processes described with reference to Figs. 1 to 16 may be implemented as software, such as a code module executing within the computer system 400.  In particular, the steps of the described methods are effected by instructions in the software that are carried out by the computer.  The instructions may be formed as one or more code sub-modules, each for performing one or more particular tasks.  The software may be stored in a computer readable medium, including the storage devices described below, for example.  The software is loaded into the computer from the computer readable medium, and then executed by the computer.  A computer readable medium having such software or computer program recorded on it is a computer program product.  The use of the computer program product in the computer preferably effects an advantageous apparatus for implementing the described methods.
The computer system 400 is formed by a computer module 401, input devices such as a keyboard 402 and mouse 403, output devices including a printer 415, a display device 414 and loudspeakers 417.  A Modulator-Demodulator (Modem) transceiver device 416 is used by the computer module 401 for communicating to and from a communications network 420, for example connectable via a telephone line 421 or other functional medium.  The modem 416 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN), and may be incorporated into the computer module 401 in some implementations.
The computer module 401 typically includes at least one processor unit 405, and a memory unit 406, for example formed from semiconductor random access memory (RAM) and read only memory (ROM).  The module 401 also includes an number of input/output (I/O) interfaces including an audio-video interface 407 that couples to the video display 414 and loudspeakers 417, an I/O interface 413 for the keyboard 402 and mouse 403 and optionally a joystick (not illustrated), and an interface 408 for the modem 416 and printer 415.  In some implementations, the modem 416 may be incorporated within the computer module 401, for example within the interface 408.  A storage device 409 is provided and typically includes a hard disk drive 410 and a floppy disk drive 411.  A magnetic tape drive (not illustrated) may also be used.  A CD-ROM drive 412 is typically provided as a non-volatile source of data.  The components 405 to 413 of the computer module 401, typically communicate via an interconnected bus 404 and in a manner which results in a conventional mode of operation of the computer system 400 known to those in the relevant art.  Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.  
Typically, the code module is resident on the hard disk drive 410 and read and controlled in its execution by the processor 405.  Intermediate storage of the module and any data fetched from the network 420 may be accomplished using the semiconductor memory 406, possibly in concert with the hard disk drive 410.  In some instances, the code module may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 412 or 411, or alternatively may be read by the user from the network 420 via the modem device 416.  Still further, the software can also be loaded into the computer system 400 from other computer readable media.  The term "computer readable medium" as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system 400 for execution and/or processing.  Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 401.  Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.
The described methods may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of the described methods.  Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.
The method 900 may be used to combine contiguous graphical objects whether the graphical objects are originally from a complex object, two objects that lie side by side or two objects that overlap.  Fig. 6 shows an example of a two-stage edge based graphics rendering system 630, which may be used to implement the method 900 and the method 1000.  The graphics rendering system 630 may be used to render a linear gradient fill such as the linear gradient fill 690 seen in Fig. 6.  The graphics rendering system 630 comprises an object compiler 670 and meta-fill dispatcher 680.  The graphics rendering system 630 also comprises a display list creation module 640, a display list 650 and a rendering module 660.  A graphics device interface 620, as shown in Fig. 6, receives a linear gradient fill 690 from a graphics application 610 and passes the linear gradient fill 690 as a number of adjacent flat-filled objects (eg., parallelogram 621) to the graphics rendering system 630.  
The object compiler 670 may be used to combine adjacent, overlapping or contiguous objects and, if suitable, form a compiled object together with an associated meta-fill, thereby removing edges in between such objects.  Once the compiler 670 has determined that no more objects may be combined into a current compiled object, then the compiler 670 may convert the compiled object into edges, a level and an associated meta-fill.  The compiled object may then be placed into a current display list 650.  
The rendering module 660 comprises a dispatcher 680.  The rendering module 660 decodes meta-fill data and generates fill information, which may be used to render one or more pixel spans within the compiled object 641.  
The method 900 of combining a plurality of objects will now be described with reference to Fig. 9.  The method may be implemented as software resident on the hard disk drive 410 and being controlled in its execution by the processor 405.  The method 900 may be implemented as one or more software modules of the compiler 670.  The objects may be received by the compiler 670 from a graphics interface, such as the graphics interface 620, in ascending z-order.  
The method 900 begins at step 910, where the processor 405 executing the compiler 670, detects a current object received from the graphics device interface 620.  At the next step 920, the processor 405 determines if the current object conforms to simple merging rules.  These rules are:
(i) The object has two parallel, non-coincident straight sides;
(ii) The object does not go outside the area between the indefinite extension of the two parallel sides identified in (i).
If the current object satisfies these rules, the current object may be merged.  If the current object may be merged, then the method 900 proceeds to step 930.  Otherwise, the method 900 proceeds to step 940.  
At step 930 the processor 405 stores the current object in memory 406.  The current object is not converted into an intermediate format at this point.  The method 900 then proceeds to step 950 and the object received at step 910 becomes a "previously stored" object.
At step 940, the processor 405 converts the current object into an edge-based format, and the method 900 continues to step 950.  At the next step 950, the processor 405 receives a next object from the graphics device interface.  The object received at step 950 becomes the "current" object.  At this point there may or may not be a "previously stored" object, depending on the path that was previously taken through the flow chart.  
The method continues at the next step 960, where if the processor 405 determines that there is a previously stored object, then the method 900 proceeds to step 970.  Otherwise, the method 900 proceeds to step 980.  
At step 970, the processor 405 determines if the current object may be combined with the previously stored object, by firstly determining if the current object conforms to the simple merging rules mentioned above with respect to step 920...  If so, then the processor 405 determines if the current object and the previously stored object satisfy predetermined criteria.  The predetermined criteria of step 970 are as follows:
(i) the parallel sides of both the current object and the previously stored object are at the same angle; and 
(ii) the current object and the previously stored object overlap over the whole length of the parallel sides of the objects or abut one another on those parallel sides.
Figs. 15A to 15E show some examples of objects (eg., 1511) satisfying the above predetermined criteria and which therefore may be combined.  Fig. 15A shows objects 1511 and 1510 which satisfy the above criteria.  The objects 1511 and 1510 do not require a path to be formed in order to describe a resulting outline 1512.  The outline 1512 may be represented by four points.  Similarly, Fig. 15B shows objects 1520 and 1522 which satisfy the above criteria and do not require a path to describe a resulting outline 1521.  Again, the outline 1521 may be represented by four points.  
Fig. 15C shows objects 1530 and 1532 which satisfy the above predetermined criteria and which may be combined.  The objects 1530 and 1532 require a path to be formed to describe a resulting compiled object 1531.  Similarly, Fig. 15D shows objects 1540 and 1542 which satisfy the above predetermined criteria and which may be combined.  The objects 1540 and 1542 require a path to be formed to describe a resulting compiled object 1541.  Similarly, Fig. 15E shows two objects 1550 and 1552 which satisfy the above predetermined criteria and which may be combined.  The objects 1550 and 1552 require a path to be formed to describe a resulting compiled object 1551.  
In contrast, Figs. 15F and 15G show some examples of objects (eg., 1571) which do not satisfy the above predetermined criteria and are not able to be combined.  Fig. 15F show examples of objects 1560 and 1561 that cannot be combined since the objects 1560 and 1561 do not satisfy the above criteria.  In particular, the objects 1560 and 1561 fail the second of the simple merging rules by going outside the area bounded by their parallel (horizontal) sides.  Similarly, Fig. 15G show examples of objects 1570 and 1571 that cannot be combined since the objects 1570 and 1571 do not satisfy the above criteria.  In particular, the objects 1570 and 1571 fail the first of the simple merging rules by not having two non-coincident sides that are parallel.
If the current object and the previously stored object satisfy the predetermined criteria of step 970, then the method 900 proceeds to step 971.  At step 971, the current object is stored in memory 406 alongside the previously stored object.  Preferably, the current object is merged with the previously stored object if their fills consist of the same, flat colour.  If the current object and the previously stored object cannot be combined at step 970, then the method 900 proceeds to step 990.  
At step 990, since the current object cannot be combined with the previously stored object, all previously stored objects are combined to form a compiled object, and the compiled object is converted into the intermediate edge-based graphics format and the method 900 then proceeds to step 980.  In step 990, when converting the object to the intermediate format, the method 900 stores fill lengths within a meta-fill structure configured within memory 406.  The fill lengths correspond to the horizontal run lengths of the individual fills of the previously stored object(s).  If there are more than one previously stored objects, the compiler 670 preferably generates a meta-fill at step 990 by creating a linked list of primitive fill data structures that describe the fills within the meta-fill.  
Fig. 11 shows a meta-fill 1110 in detail.  The meta-fill 1110 comprises all of the data necessary to recall a particular fill entry at any point within a compiled object.  The meta-fill 1110 comprises a header 1120.  The header 1120 comprises a tracking point 1121 and a tracking point DX 1122.  The tracking point 1121 may be used to indicate a starting location of a first fill 1123 within the meta-fill 1110 for a specified scanline.  The starting location of a first fill within the meta-fill 1110 for a specified scanline enables the compiled object associated with the meta-fill 1110 to be rendered as will be described in more detail below.  The tracking point 1121 is updated for a current scanline according to the tracking point DX 1122.  The tracking point DX 1122 represents the slope of parallel sides of objects that were originally grouped to form the compiled object represented by the meta-fill 1110.  The tracking point is set to be the intersection of the leftmost parallel side of the object with the topmost scanline on which the object exists.  The tracking point DX 1122 may be used by the dispatcher 680 to track the location of a first fill within the meta-fill 1110.  If the position of the first fill within the meta-fill is known then all other fills of the compiled object may be determined.  The header 1120 also comprises a pointer 1133 to the next fill 1123.  
Individual primitive fills 1123 are attached to the header 1120 as a linked list.  Each of the individual fills are linked to one another, and each primitive fill comprises a header (eg., header 1129).  The header 1129 comprises at least a size variable 1131 representing the length of a pixel run for the particular fill within the meta-fill 1110.  The size variable 1131 is used by the dispatcher 680 when rendering the meta-fill 1110 to pixels, and ensures that correct sized pixel runs are output for each fill within the meta-fill 1110 as will be explained in more detail below.  The compiler 670 determines the pixel lengths of each individual fill within the meta-fill 1110 by simply determining a horizontal distance between the parallel sides of each object added to the meta-fill 1110.  The header 1129 also comprises a fill type 1135 and associated parameters and a pointer 1137 to the next fill 1125.  Once the meta-fill 1110 has been generated, the meta-fill 1110 is added to a display list along with the edges and level data for a compiled object.
In other embodiments other data structures such as tables or arrays could be used for the meta-fill.
Note that the level of the compiled object created in step 990 is equal to the level of the earliest (lowest level) previously stored object.
The method 900 continues at the next step 980, where the processor 405 determines if the current object conforms to the simple merging rules, as in step 920.  If the current object was previously assessed at step 970 and it was determined that the current object may be merged with another object, then the processor 405 may use the result of that analysis to determine if the current object may be merged.  If the processor 405 determines that the current object may be merged with another object at step 980, then the method 900 proceeds to step 981.  Otherwise, the method 900 proceeds to step 985 where the current object is converted to the intermediate format.  Execution then proceeds to step 982.
At step 981, the current object is stored in memory 406.  Then at the next step 982, if there are no more objects for the graphics rendering system 630 to process then the method 900 proceeds to step 983.  Otherwise the method 900 returns to step 950.  At step 983, all previously stored objects are combined to form a compiled object, as in step 990, and the compiled object is converted into the intermediate edge-based format with an associated meta-fill.  
Edge and level data for the compiled object are determined at step 990 and/or 983 from the outline of the compiled object and not the properties of the individual objects (ie., the previously stored objects).  Instead of a standard primitive fill, a meta-fill is used to describe the fill data within the compiled object.  Fig. 12 shows an example of a compiled object 1210 and an associated meta-fill 1215.      
Fig. 7A shows an original edge based object 710.  Fig. 7B shows the object 710 stored in a conventional manner as fills 720, edges 722 and levels 724.  In contrast, the object 710 may be stored as a compiled object represented by fills 730, edges 732 and a level 734, as shown in Fig. 7C.  The edges 732 and level 734 of Fig. 7C representing the original object 710 require less memory than the edges 722 and levels 724 of Fig. 7B.  
The dispatcher 680 of the rendering module 660 determines which fill is to be rendered for a specific pixel and scanline position.  When a top most active level to be rendered has a meta-fill associated with the level, the dispatcher 680 may be used to decode the meta-fill.  
As described above, a meta-fill comprises a tracking point 1121 that is tracked by the dispatcher 680.  The tracking point 1121 moves parallel to the parallel sides of objects that were originally combined.  Using the tracking point 1121 the dispatcher 680 may determine which fill to use within the meta-fill 1110 for any position within a compiled object being rendered.
When all or part of a compiled object is to be rendered, rendering information representing the compiled object is passed to the dispatcher 680.  The dispatcher 680 uses a current x-position of the rendering module 660, the tracking point 1121 for the compiled object and the pixel widths of the individual fills (eg., 1123) within the meta-fill 1110 to determine a current fill and the number of pixels to be rendered from the current fill.  The x position within the meta-fill 1110 may not necessarily correspond to the same point on a scanline as the tracking point 1121, since there may be other objects occluding the meta-fill 1110 or the meta-fill 1110 may contain a clip object.  For example, Fig. 12 shows the compiled object 1210 with a clipping region 1220.  
Fig. 10 is a flow diagram showing a method 1000 of rendering a compiled object.  The method 1000 may be implemented as software resident on the hard disk drive 410 and being controlled in its execution by the processor 405.  The method 1000 may be implemented as one or more software modules of the dispatcher 680.
The method 1000 begins at the first step 1010, where the dispatcher 680 receives a meta-fill.  The meta-fill may be received from the rendering module 660.  The rendering module 660 may specify the number of pixels to be rendered, the output format and a current scanline position of the rendering module.  The rendering module 660 may also configure an output buffer within memory 406 for placing rendered pixel data.  
The method 1000 then proceeds to step 1015 where the tracking point (eg., 1121) of the meta-fill is updated according to a current scanline being rendered.  The dispatcher 680 updates the tracking point for the meta-fill by determining the distance between a current y-position of the tracking point of the meta-fill and the y-position of the current scanline.  Then the dispatcher 680 multiplies the determined distance (which may be zero) by the tracking point DX (eg., 1122).  The result of the multiplication is then added to the current tracking point x-position to determine the new tracking point x-position.  The new y-position of the tracking point for the meta-fill is updated to coincide with the current y position of the current scanline.  At the next step 1020, a current render position of the rendering module 660 is compared to the tracking point of the meta-fill to determine the number of pixels the current render position is from the tracking point.  The determination may be made at step 1020 by subtracting the updated tracking point x-position from the current render x-position.  
The method 1000 continues at the next step 1030, where the processor 405 determines an active fill from the fills of the meta-fill.  The active fill is the fill of the meta-fill that corresponds to current pixel data to be rendered.  At the next step 1040, the number of pixels to render using the active fill is determined.  The number of pixels to render using the active fill is determined as the minimum of the number of pixels that the rendering module 660 requests to be rendered and the number of pixels remaining in the active fill.  The number of pixels remaining in the active fill is determined on the basis of a maximum x-position of the active fill minus the current renderer x-position.  
Once the number of pixels to be rendered is determined, the method 1000 proceeds to step 1050.  At step 1050, the required pixel run is rendered.  In order to generate pixel data, the dispatcher 680 passes the active fill to a native rendering function according to the fill type of the active fill.  Also at step 1050, the current render x-position and the number of pixels to be rendered are updated.  The method 1000 continues at the next step 1060, where if there are still more pixels to be rendered, then the method 1000 proceeds to step 1070.  Otherwise, the method 1000 concludes.  At step 1070, the processor 405 retrieves a next fill in the meta-fill.  The fill retrieved at step 1070 becomes the active fill.  Following step 1070, the method 1000 proceeds to step 1040.
As an example, Fig. 8A shows a page 830 comprising a compiled object 820 in the form of a parallelogram.  The compiled object 820 has a circle object 810 occluding part of the compiled object 820.  The circle object 810 comprises a white flat fill.  The compiled object 820 has four fills 807, 809, 811 and 813, which may be included within one meta-fill 835, as shown in Fig. 8B.  
The meta-fill 835 comprises a header 837 comprising a tracking point variable 844 indicating the starting location (i.e., pixel 100) of the first fill 807 within the meta-fill 835 for a specified scanline (i.e., 300).  The header 837 comprises a tracking point DX 865.  The header 837 also comprises a pointer to a fill structure 838 describing the next fill 809. 
The fill structure 838 comprises a header 839.  The header 839 describes the fill type using a fill type variable 846.  The fill type variable 846 indicates that the fill 807 is a pattern fill.  The header 839 also comprises a size variable 847 representing the length of a pixel run for the fill 807.  The fill 807 covers twenty (20) pixels.    The fill structure 838 also comprises the striped pattern fill data 861.  Finally, the header 839 comprises a pointer 848 to a next fill structure 841 describing the next fill 809.            
The fill structure 841 comprises a header 843.  The header 843 describes the fill type using a fill type variable 849.  The fill type variable 849 indicates that the fill 809 is a pattern fill.  The header 841 also comprises a size variable 850 indicating that the length of a pixel run for the fill 809 is one hundred (100) pixels.      The fill structure 841 also comprises the cross hatch pattern fill data 862.  Finally, the header 843 comprises a pointer 851 to a next fill structure 845 describing the next fill 811.
The fill structure 845 comprises a header 852.  The header 852 describes the fill type using a fill type variable 853.  The fill type variable 853 indicates that the fill 811 is a pattern fill.  The header 852 also comprises a size variable 854 representing the length of a pixel run for the fill 811.  The fill 811 covers one-hundred and fifty (150) pixels, as indicated by the size variable 854.  The fill structure 845 also comprises the dot pattern fill data 863.  Finally, the header 852 comprises a pointer 855 to a next fill structure 856 describing the next fill 813.  
The fill structure 856 comprises a header 857.  The header 857 describes the fill type using a fill type variable 858.  The fill type variable 858 indicates that the fill 813 is a flat fill.  The header 857 also comprises a size variable 859 representing the length of a pixel run for the fill 813.  The fill 813 covers forty (40) pixels, as indicated by the size variable 859.  The fill structure 856 also comprises the flat fill data 864.  Finally, the header 857comprises a pointer 860 to a next fill structure.  However, in the example of Figs. 8A and 8B, there is no further fill, so the pointer 860 is null-valued.
The circle object 810 has a higher z-order than the meta-fill 835 and is therefore occluding part of the compiled object 820.  In response to a current rendering position of the rendering module 660 crossing a point 805 on the circle object 810, the fill associated with a first pixel following point 805 needs to be determined.  At the point 805, the y position is three-hundred (ie., the current scanline is three-hundred (300)) and the x position is two-hundred and sixty-five (265).  The compiler 670 determines that the fill for the compiled object 820 is the meta-fill 835 and passes the fill to the dispatcher 680 for decompiling, as at step 1010 of the method 1000.  The dispatcher 680 updates the tracking point of the meta-fill 835 to coincide with the tracking point 815 of the compiled object 820 for the current scanline (ie., scanline three-hundred (300)), as at step 1015 of the method 1000.  
The dispatcher 680 updates the tracking point variable 844 for the current scanline by determining the distance between a current y-position of the tracking point variable 844 of the meta-fill 835 and the y-position of the current scanline (ie., scanline three-hundred (300)) being rendered.  Then the dispatcher 680 multiplies the determined distance (which may be zero) by the tracking point DX 865 to determine a new x position for the tracking point variable 844 of the meta-fill 835.  The new y-position of the tracking point variable 844 for the meta-fill 835 is updated to coincide with the current y position of the current scanline.  In the example of Figs. 8A and 8B, the tracking point variable 844 for the tracking point 815 of the current scanline is (100, 300), as described above.  
The dispatcher 680 may use the determined tracking point variable 844 indicating the tracking point 815 to determine a currently "active" fill, as at step 1030 of the method 1000.  The currently active fill is the fill to be rendered for the first pixel following point 805.  The dispatcher 680 determines the distance between the x-position at point 805 and the x-position of the tracking point 815.  In the example of Fig. 8A, at the point 805, the x-position is one-hundred and sixty-five (165) pixels (ie., 265 - 100) from the tracking point 815.  The dispatcher 680 then goes through a list of linked fill structures 838, 841, 845 and 856 associated with the meta-fill 835 to determine the fill that is associated with the 165th pixel from the tracking point 815.  The dispatcher 680 determines the fill associated with the 165th pixel by accumulating individual pixel run lengths of the linked fills until the current fill covers the 165th pixel.  For the compiled object 820, the first fill 807 covers twenty (20) pixels, the second fill 809 covers one-hundred (100) pixels, the third fill 811 covers one-hundred and fifty (150) pixels and the final fill 813 covers forty (40) pixels, as described above.  In the example of Figs. 8A and 8B, the third fill 811 will cover the 165th pixel from the tracking point 815.  The third fill 811 is therefore referred to as the currently active fill.  As seen in Fig. 8A, the third fill 811 starts at the 120th pixel from the tracking point 815.  The line marked Ax in Fig. 8A is one-hundred and twenty (120) pixels in length.  With reference to the page bounds 830, the 120th pixel corresponds to pixel number two-hundred and twenty (220) on the current scanline (ie., scanline three-hundred (300)).  Since the current rendering position of the rendering module 660 is pixel number two-hundred and sixty-five (265), the dispatcher 680 may determine that forty-five (45) pixels (ie., 265 - 220) of the third fill 811 have been passed, as shown by Lx on Fig. 8A.  As seen in Fig. 8A, Fx represents the number of pixels to be rendered for the currently active fill 811.  The dispatcher 680 determines that the number of pixels to be rendered for the currently active fill 811 is one-hundred and five (105) pixels (ie., 150 - 45), as at step 1040 of the method 1000.
The dispatcher 680 then calls on the rendering module 660 to use native rendering functions to render the one-hundred and five (105) pixels of the third fill 811 represented by Fx, as at step 1050 of the method 1000.  Once the rendering module 660 has finished rendering the one -hundred and five (105) pixels according to the currently active fill 811, if the dispatcher 680 determines that there are more pixel runs of the current scanline to be rendered then the dispatcher 680 determines a next active fill as at step 1070 of the method 1000.
As described above, graphical objects may be combined to form a compiled object, thereby removing redundant edges.  Since the attributes of a meta-fill only have to be determined once, at a high level, unlike edges which need to be constantly sorted and tracked for each scanline, rendering of a compiled object is much more efficient than conventional rendering methods which must sort and track many more edges.
The compiler 670 may at step 983 and / or 990 combine graphical objects with different fill types.  The compiler 670 combines the edges of such objects and treats fills associated with the objects as separate entities that belong to the same object.  Therefore, when combining bitmaps, no extra image manipulation or copying needs to be performed.  The fills associated with objects may be processed separately and stored separately but will be linked together by the compiler 670.  For example, Fig. 16 shows a meta-fill 1660 that links two bitmaps 1630 and 1640 generated by the graphics device interface 620 of Fig. 6.  In the example of Fig. 16, an original bitmap 1620, created by a graphics application such as the graphics application 610, is passed by the graphics device interface 620 as the two separate bitmaps 1630 and 1640.  The compiler 670 recognises that the bitmaps 1630 and 1640 lie side by side and so generates the meta-fill 1660 from the two bitmaps 1630 and 1640.  In contrast, conventional rendering methods would combine the bitmaps 1630 and 1640 by copying data of one bitmap (eg., bitmap 1630) to the other bitmap 1640, which is inefficient.
As also described above, conventional rendering methods produce many gradient fills from a non-linear gradient fill such as the non-linear gradient fill 510.  However, as described above, the gradient fill 510 may be processed as a single compiled object, with multiple fill elements.  As such, redundant edges may be removed whilst retaining relevant linear gradients in a meta-fill.  For combining simple flat fills, the compiler 670 is no longer limited to just combining objects of the same colour.  The compiler 670 may combine objects with different colours and even objects with different fill types, since fills will again be linked.  Therefore, whilst edges of objects have been combined into one, all necessary fill information will still be presented to the rendering module 660.
Fig. 13 shows six primitive objects 1310, 1320, 1330, 1340, 1350 and 1360.  The conventional rendering system 330 processes each of the objects 1310 to 1360 as two edges (eg., edge 1311 and edge 1312 for the object 1310).  Each edge 1311 has associated level data 1313 and fill data 1314.  In contrast, Fig. 14 shows a compiled object 1410 formed from the objects 1310 to 1360.  The compiled object has an associated meta-fill 1415, as seen in Fig. 14.  The rendering module 660 processes the compiled object 1410 as a single object and therefore only has knowledge of the edges 1411 and 1412 that describe an outline 1413 of the compiled object 1410.
To render the primitive objects 1310 to 1360, a conventional edge based rendering module such as the module 360 updates the position of each edge (eg., the edge 1311) of each object for every scanline.  For each individual scanline, as the rendering module 360 encounters a left edge such as the edge 1311, the level data 1313 has to be loaded and a pixel run calculated from the fill data 1314.  In contrast, by encoding and decoding a meta-fill such as the meta-fill 1415, the rendering module 660 only has to process two edges and only needs to load a single level.  For example, the rendering module 660 does not need to individually track the edges of each of the objects 1310 to 1360, since all of the edges (eg., the edges 1311 and 1312) are parallel.  As such, fill data may always be determined in relation to a first fill 1417 within the meta-fill 1415, which greatly reduces the amount of effort required by the rendering module.  The dispatcher 680 may produce pixel data in an efficient manner.  When using a meta-fill such as the meta-fill 1415 the only updating that is required per scanline is that of the tracking point (eg., 1121).
For conventional graphics rendering systems, such as the graphics rendering system 330, which carry out RGB to CMYK colour conversion, there are a number of known methods for representing a CMYK colour converted linear gradient fill.  One method is to convert the RGB gradient fill into a bitmap in RGB space and then convert each pixel colour to CMYK to produce a colour corrected bitmap.  Another method is to sample many points in the RGB colour space along the gradient fill and colour convert those points to generate many small linear CMYK gradient fills that approximate a colour converted gradient fill.  Still another method is to sample the RGB gradient fill and generate a number of CMYK flat fills that represent the original gradient fill.
Representing the linear gradient fill as a CMYK bitmap is highly inefficient compared to the original RGB gradient fill description.  Further, breaking the RGB gradient fill up into many small CMYK gradient fills or CMYK flat fills has the disadvantage of producing many edges between adjacent gradient fills and therefore dramatically slowing a conventional rendering module such as the rendering module 360.  However, many CMYK gradient fills or flat fills may be represented as a single meta-fill such as the meta-fill 1415 described above.  Using such a meta-fill 1415, removes additional edges introduced into an object during colour space conversion.
As more and more objects are combined into a compiled object such as the object 1413, the longer the pixel runs for a compiled object become.  Many compiled objects will greatly benefit from longer pixel runs, especially when cached pixel runs can be reused from previous scanlines.  For example, combining flat fills of the same colour into one compiled object will generate a larger pixel run of the object and better cache reuse.  In addition, since some rendering modules are limited in the amount of objects which the rendering modules can render on a page, generating a compiled object and associated meta-fill as described above may enable the rendering of a page by hardware without the need to form a software fallback job (ie., a job that is rendered purely by software since a current page is too complex for a target device to render).
The aforementioned preferred method(s) comprise a particular control flow.  There are many other variants of the preferred method(s) which use different control flows without departing the spirit or scope of the invention.  Furthermore one or more of the steps of the preferred method(s) may be performed in parallel rather sequential.
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.  
6. Brief Description of the Drawings
Some aspects of the prior art and one or more embodiments of the present invention are described with reference to the drawings and appendices, in which: 
Fig. 1 shows conventional relationship between a conventional software application, a graphics device interface layer, a graphics rendering system and a target device;
Fig. 2A shows an example of a radial gradient fill;
Fig. 2B shows an example of a non-linear gradient fill;
Fig. 2C shows an example of a linear gradient fill;
Fig. 3 shows a conventional graphics rendering system;
Fig. 4 is a schematic block diagram of a general purpose computer upon which arrangements described can be practiced;
Fig. 5A shows a non-linear gradient fill;
Fig. 5B shows two linear gradient fills produced from the non-linear gradient fill of Fig. 5A;
Fig. 5C shows a number of linear gradient fills;
Fig. 6 shows a two-stage edge based graphics rendering system;
Fig 7A shows an original edge based object;
Fig. 7B shows the object of Fig. 7A stored in a conventional manner as fills, edges and levels;
Fig. 7C shows the object of Fig. 7A stored as a compiled object represented by fills, edges and a level;
Fig. 8A shows a compiled object with a circle occluding part of the compiled object;
Fig. 8B shows the meta-fill describing fills of the compiled object of Fig. 8A;
Fig. 9 shows a method of combining a plurality of objects to generate a compiled object;
Fig. 10 is a flow diagram showing a method of rendering a compiled object;
Fig. 11 is a schematic diagram showing a meta-fill;
Fig. 12 shows an example of an object which is compiled with an associated meta-fill; 
Fig. 13 shows six primitive objects together with associated edge and level data;
Fig. 14 shows a compiled object formed from the objects of Fig. 13 and the associated meta-fill;
Figs. 15A to 15E show some examples of objects which may be combined;
Figs. 15F and 15G show some examples of objects are not able to be combined; andFig. 16 shows an example meta-fill that links two bitmaps.
1. A method of rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order, and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said method comprising the steps of:
combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more fill data structures representing the fills associated with said graphical objects; and 
rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.  
2. A method according to claim 1, wherein said grouped object outline follows one or more of said predetermined object outlines or parts thereof.
3. A method according to claim 1, wherein said objects are consecutive in z-order and said grouped object is assigned the lowest z-order among said objects.
4. A method according to claim 1, further comprising the step of determining if said objects satisfy predetermined criteria.
5. A method according to claim 1, wherein one or more graphical objects that have the same single coloured fills are represented as one or more single coloured fills in said compound fill.
6. A method according to claim 1, wherein one or more graphical objects that have a linear colour change are represented as one or more linear blend fills in said compound fill.
7. A method according to claim 4, wherein one of said predetermined criteria is that each of said objects has two parallel sides.
8. A method according to claim 7, wherein one of said predetermined criteria is that each of said parallel sides has the same angle of orientation.
9. A method according to claim 8, wherein one of said predetermined criteria is that each of said objects (i) overlap or (ii) abut over the whole length of said parallel sides.
10. A method according to claim 1, further comprising the step of storing lengths of pixel runs in said compound fill.
11. A method according to claim 1, wherein said fills are represented in said compound fill as a linked list of fill data structures that describe said fills.
12. A method according to claim 11, further comprising the step of storing a pointer to a first fill in said data structure.
13. A method according to claim 1, wherein each of said fills are flat fills.
14. A method according to claim 1, wherein the object outline for each of said graphical objects comprises one or more edges.
15. A method according to claim 1, wherein the object outline is a path.
16. A method according to claim 1, wherein the object outline is a polygon defined by a plurality of points.
17. A compound fill for rendering a graphical object, said graphical object comprising a predetermined object outline and said compound fill, the predetermined object outline defining an area in which said graphical object is filled, wherein said compound fill is configured as a data structure containing a plurality of fills, said fills defining a manner in which said graphic object is to be filled upon rendering.
18. A compound fill according to claim 17, wherein said graphical object is formed from a plurality of graphical objects.
19. A compound fill according to claim 17, wherein said data structure is a linked list.   
20. A method according to claim 1, further comprising the step of storing a tracking point in said compound fill.
21. A method according to claim 20, wherein said tracking point is used to determine a current fill within said compound fill for rendering said grouped object.
22. An apparatus for rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order,  and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said apparatus comprising:
combining means for combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more  fill data structures representing the fills associated with said graphical objects; and 
rendering means for rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.
23. A computer program for rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order,  and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said program comprising:
code for combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more fill data structures representing the fills associated with said graphical objects; and 
code for rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.
24. A computer program product including a computer readable medium having recorded thereon a computer program for rendering a plurality of graphical objects, each of said graphical objects comprising a predetermined object outline, a predetermined z-order,  and an associated fill, the object outline for a particular object defining an area in which said particular object is filled, said program comprising:
code for combining each of said objects to form a grouped object, said grouped object comprising a grouped object outline and an associated compound fill, said compound fill comprising one or more fill data structures representing the fills associated with said graphical objects; and 
code for rendering said grouped object according to said grouped object outline, wherein one or more fills used to render said grouped object are determined according to said compound fill.
1. Abstract
A method (900) of combining a plurality of objects is disclosed.  The method (900) efficiently combines a set of contiguous graphical objects to generate a high level compiled object representing the combination of the contiguous objects.  The method (900) may be used to combine such contiguous objects even if the objects have different fill types.  The method (900) outputs the compiled object to a display list.  The compiled object has an associated meta-fill (835).  The meta-fill (835) is a compound fill, which may be used to describe a collection of fills associated with the compiled object.  
2005267639.tif 000032
2005267639.tif 000033
2005267639.tif 000034
2005267639.tif 000035
2005267639.tif 000036
2005267639.tif 000037
2005267639.tif 000038
2005267639.tif 000039
2005267639.tif 000040
2005267639.tif 000041
2005267639.tif 000042
2005267639.tif 000043
2005267639.tif 000044
2005267639.tif 000045
2005267639.tif 000046
2005267639.tif 000047
2005267639.tif 000048
2005267639.tif 000049