(57)【要約】【課題】印刷データに複雑な描画コマンドが含まれている場合であっても、レンダリング処理を高速化する。【解決手段】本発明のレンダリング装置は、印刷データに含まれるオブジェクトをレンダリングするレンダリング装置であって、前記オブジェクトのエッジを示すエッジ情報に基づいて、前記印刷データにおける走査ラインと交差する前記エッジを管理する管理手段と、前記管理されるエッジを複数のグループに分割する分割手段と、前記走査ラインが移行することに応じて、前記管理されるエッジの座標を、前記分割された複数のグループごとに更新する座標更新手段と、前記管理されるエッジを、前記分割された複数のグループごとにソートするソート手段と、を有することを特徴とする。【選択図】図２
2019087163.tif 000002
【特許請求の範囲】
【請求項１】
印刷データに含まれるオブジェクトをレンダリングするレンダリング装置であって、
前記オブジェクトのエッジを示すエッジ情報に基づいて、前記印刷データにおける走査ラインと交差する前記エッジを管理する管理手段と、
前記管理されるエッジを複数のグループに分割する分割手段と、
前記走査ラインが移行することに応じて、前記管理されるエッジの座標を、前記分割された複数のグループごとに更新する座標更新手段と、
前記管理されるエッジを、前記分割された複数のグループごとにソートするソート手段と、を有する
ことを特徴とするレンダリング装置。
【請求項２】
前記分割手段は、前記管理されるエッジの数が所定の閾値以上である場合、前記管理されるエッジを複数のグループに分割することを特徴とする請求項１に記載のレンダリング装置。
【請求項３】
前記分割手段は、前記印刷データにおけるページの幅を基準に前記管理されるエッジを複数のグループに分割することを特徴とする請求項１または２に記載のレンダリング装置。
【請求項４】
前記管理手段は、前記オブジェクトのエッジが、前記走査ラインが移行する直前に前記印刷データにおける第１のページに位置し、前記走査ラインが移行した後に前記印刷データにおける第２のページに位置する場合、
前記走査ラインが移行することに応じて、前記エッジに対応するエッジ情報を、前記第１のページに対応するグループから、前記第２のページに対応するグループに移動させる
ことを特徴とする請求項３に記載のレンダリング装置。
【請求項５】
前記分割手段は、前記印刷データにおけるページの幅が所定の閾値以上である場合、前記管理されるエッジのうち当該ページに対応するエッジを複数のグループに分割することを特徴とする請求項１から４のいずれか１項に記載のレンダリング装置。
【請求項６】
前記印刷データにおけるページの幅は、前記印刷データの印刷に用いられる記録媒体の幅に基づいて設定されることを特徴とする請求項３から５のいずれか１項に記載のレンダリング装置。
【請求項７】
前記分割されたグループにおけるそれぞれのエッジの数が所定の閾値よりも少ない場合、前記分割された複数のグループを結合する結合手段をさらに有することを特徴とする請求項１から６のいずれか１項に記載のレンダリング装置。
【請求項８】
前記管理手段は、前記分割された複数のグループでそれぞれ管理されるエッジ情報の数の差が所定の閾値以上である場合、前記管理されるエッジ情報が多いグループから、前記管理されるエッジ情報が少ないグループに前記エッジ情報を移動させることを特徴とする請求項１から７のいずれか１項に記載のレンダリング装置。
【請求項９】
前記印刷データの座標系において走査方向をＸ軸、走査方向と直交する方向をＹ軸としたとき、前記エッジ情報は、前記走査ラインと前記オブジェクトのエッジとが交差する位置に対応するＸ座標値を少なくとも含み、
前記座標更新手段は、前記走査ラインがＹ軸方向に移行することに応じて、前記エッジ情報に含まれるＸ座標値を更新し、
前記ソート手段は、前記分割された複数のグループでそれぞれ管理されるエッジ情報を、前記エッジ情報に含まれるＸ座標値が昇順となるようにソートする
ことを特徴とする請求項１から８のいずれか１項に記載のレンダリング装置。
【請求項１０】
前記オブジェクトのエッジは、該オブジェクトの開始エッジおよび終了エッジの対で構成されることを特徴とする請求項１から９のいずれか１項に記載のレンダリング装置。
【請求項１１】
印刷データに含まれるオブジェクトをレンダリングするレンダリング方法であって、
前記オブジェクトのエッジを示すエッジ情報に基づいて、前記印刷データにおける走査ラインと交差する前記エッジを管理する管理ステップと、
前記管理されるエッジを複数のグループに分割する分割ステップと、
前記走査ラインが移行することに応じて、前記管理されるエッジの座標を、前記分割された複数のグループごとに更新する座標更新ステップと、
前記管理されるエッジを、前記分割された複数のグループごとにソートするソートステップと、を有する
ことを特徴とするレンダリング方法。
【請求項１２】
コンピュータを、請求項１から請求項１０のいずれか１項に記載のレンダリング装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、印刷データに含まれるオブジェクトのレンダリング技術に関する。
【背景技術】
【０００２】
従来より、ＰＤＬ（Ｐａｇｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ）で記述された印刷データに含まれるオブジェクトをレンダリングするレンダリング技術が知られている。オブジェクトは、ページにおける任意の位置に文字、図形、画像などを描画する描画命令によって構成される。オブジェクトの輪郭（以下「エッジ」と記す）は、そのエッジの開始点と、エッジの開始点からの変位量とによって表される。このようなエッジ情報はリスト化され、このリスト化されたエッジ情報は中間データと呼ばれる。レンダリング機能を実装しているプリンタは、このような中間データを、プリンタが処理可能なビットマップ画像データに展開してから、プリンタ用紙などへの印刷を行う。このような印刷手法は、例えば特許文献１に開示されている。
【０００３】
一般的に、中間データがビットマップ画像データに展開される際、走査変換と呼ばれる処理が行われる。走査変換処理では、ページの上部から下部まで走査ラインを移行させつつ、走査ラインとエッジとが交差する位置を示す座標値が順次導出され、さらに導出された座標値が走査ラインごとにソートされる。そして、ページの上部から下部までの走査ラインごとに、ソートされた座標間の色塗り処理を繰り返すことにより、ビットマップ画像データが生成される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−１３７８２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、走査変換処理におけるソートは、複数のオブジェクトが重なる場合に、いずれのオブジェクトが前方に位置し、いずれのオブジェクトが後方に位置するかを特定する、オブジェクトの重なり解決のために行われる。印刷データにオブジェクトが大量に含まれている場合のように、ソート処理の対象となるエッジの数が増加すると、ソート処理に必要な時間は指数関数的に増加してしまうという課題があった。
【０００６】
本発明は上記課題に鑑みなされたものであり、走査変換におけるソート処理に必要な時間を短縮することができる。
【課題を解決するための手段】
【０００７】
本発明のレンダリング装置は、印刷データに含まれるオブジェクトをレンダリングするレンダリング装置であって、前記オブジェクトのエッジを示すエッジ情報に基づいて、前記印刷データにおける走査ラインと交差する前記エッジを管理する管理手段と、前記管理されるエッジを複数のグループに分割する分割手段と、前記走査ラインが移行することに応じて、前記管理されるエッジの座標を、前記分割された複数のグループごとに更新する座標更新手段と、前記管理されるエッジを、前記分割された複数のグループごとにソートするソート手段と、を有することを特徴とする。
【発明の効果】
【０００８】
本発明のレンダリング手法によれば、走査変換におけるソート処理に必要な時間を短縮することができる。
【図面の簡単な説明】
【０００９】
【図１】実施形態１におけるプリントシステムの構成例を示す模式図である。図１（ａ）はプリントシステムの構成例を示す模式図である。図１（ｂ）はレンダリング装置のハードウェア構成例を示す模式図である。
【図２】実施形態１におけるレンダリング装置の機能構成例を示す図である。
【図３】実施形態１におけるレンダリング手順例を示すフローチャートである。
【図４】図４（ａ）は本実施形態におけるオブジェクト例を表す模式図である。図４（ｂ）は本実施形態におけるリストの内容例を表す模式図である。図４（ｃ）は本実施形態におけるエッジ情報の内容例を表す模式図である。
【図５】実施形態１における画像生成手順例を示すフローチャートである。
【図６】図６（ａ）は本実施形態におけるオブジェクト例を表す模式図である。図６（ｂ）は本実施形態におけるＡＥＬの内容例を表す模式図である。図６（ｃ）は本実施形態におけるエッジ情報の内容例を表す模式図である。
【図７】図７（ａ）は本実施形態におけるオブジェクト例を表す模式図である。図７（ｂ）は本実施形態におけるＡＥＬの内容例を表す模式図である。
【図８】図８（ａ）は本実施形態においてＡＥＬが分割される様子を表す模式図である。図８（ｂ）は本実施形態においてＡＥＬが結合される様子を表す模式図である。
【図９】実施形態１におけるＡＥＬの更新手順例を示すフローチャートである。
【図１０】実施形態１においてエッジ情報が移動される様子を示す模式図である。図１０（ａ）は本実施形態におけるオブジェクト例を表す模式図である。図１０（ｂ）は本実施形態におけるＡＥＬの内容例を表す模式図である。
【図１１】実施形態１においてエッジ情報がソートされる様子を示す図である。図１１（ａ）は本実施形態におけるオブジェクト例を表す模式図である。図１１（ｂ）は本実施形態におけるＡＥＬの内容例を表す模式図である。
【図１２】実施形態１のレンダリング手法を適用した場合の効果を説明する図である。
【図１３】実施形態２におけるＡＥＬ更新手順例を示すフローチャートである。
【図１４】実施形態２においてエッジ情報が移動される様子を示す模式図である。図１４（ａ）は本実施形態におけるオブジェクト例を表す模式図である。図１４（ｂ）は本実施形態におけるＡＥＬの内容例を表す模式図である。
【発明を実施するための形態】
【００１０】
［実施形態１］
以下、本発明を実施するための形態について図面を参照して説明する。ただし、この実施形態に記載されている構成はあくまで例示であり、本発明の範囲を必ずしもそれらに限定する趣旨のものではない。
【００１１】
（プリントシステムの構成）
図１（ａ）は、本実施形態におけるレンダリング装置を含むプリントシステムの構成例を示す模式図である。本実施形態のプリントシステム１において、情報処理装置１０は、ネットワーク２０を介してＰＤＬデータをレンダリング装置１００に送信する。ネットワーク２０は、無線ＬＡＮ、有線ＬＡＮ、ＵＳＢケーブルなど、ＰＤＬデータを送信可能であればその形態は問わない。レンダリング装置１００は、ネットワーク２０を介して送信されたＰＤＬデータを入力として、入力されたＰＤＦデータにレンダリング処理を行う。
【００１２】
図１（ｂ）は、レンダリング装置のハードウェア構成例を示すブロック図である。レンダリング装置１００は、ＣＰＵ１０１と、ＲＡＭ１０２と、入出力インターフェース（以下インターフェースは「Ｉ／Ｆ」と記す）１０３と、補助記憶装置１０４と、ＡＳＩＣ１０５などを備える。これらレンダリング装置１００の各構成はデータ転送バス１０６によって相互に通信可能に連結される。なお、図１（ｂ）に示されるハードウェア構成と同様の構成であれば、レンダリング装置１００は、ＰＣ、サーバ、スマートフォン、タブレット、プリンタなど機器の種別は限定されない。レンダリング装置１００がプリンタの場合、図１（ｂ）に示されるハードウェア構成に加えて、プリンタ用紙などの記録媒体上に画像を形成するためのプリンタ部などの構成が含まれることになるが、これらは本実施形態の主眼ではないため説明を省略する。
【００１３】
ＣＰＵ１０１は、ロードされたプログラムを実行してレンダリング装置１００を統括的に制御する。ＣＰＵ１０１は、特に、入力されたＰＤＬデータにレンダリング処理を実行する。ＲＡＭ１０２は主記憶装置である。本実施形態では、レンダリング処理で用いられるＰＤＬデータ、中間データ、および一時変数がＲＡＭ１０２保存される。また、本実施形態では、レンダリング装置１００の統括制御に用いられるプログラムも不図示のＲＯＭなどからＲＡＭ１０２にロードされる。入出力Ｉ／Ｆ１０３は、情報処理装置１０などの外部装置とのデータ転送を制御する。特に、入出力Ｉ／Ｆ１０３は、有線ＬＡＮや無線ＬＡＮなどに接続されて、情報処理装置１０からＰＤＬデータの入力を受け付けるとともに、レンダリング処理の結果得られたビットマップ画像データを情報処理装置１０に送信する。補助記憶装置１０４には、例えばハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｉｓｋ）などを適用することができ、レンダリング装置１００の動作制御用プログラム、レンダリング処理で生成される中間データおよびビットマップ画像データを保存する。また、ＲＡＭ１０２で保存するには容量が大きすぎるデータについても、一時的に補助記憶装置１０４に保存される。ＡＳＩＣ１０５は、レンダリング処理を高速化するために設けられており、本実施形態では、中間データからビットマップ画像を生成する画像処理を実行する。ＡＳＩＣ１０５が担うべき役割は、ＣＰＵ１０１でも代替されうる。
【００１４】
（レンダリング処理）
以下、図２の機能ブロック図および図３のフローチャートを参照して、本実施形態におけるレンダリング処理の詳細について説明する。  
【００１５】
図２は、本実施形態におけるレンダリング装置１００の機能構成例を示すブロック図である。図２に示される各ブロックの機能は、ＣＰＵ１０１またはＡＳＩＣ１０５がレンダリングプログラム２００のプログラムコードを読み出して実行することにより実現される。あるいはまた、図２に示される各ブロックの機能は、ＣＰＵ１０１とＡＳＩＣ１０５が協働して動作することにより実現されてもよい。レンダリングプログラム２００は、ＰＤＬ解釈部２１０と、中間データ生成部２２０と、画像生成部２３０とを含む。さらに、画像生成部２３０は、ＡＥＬ管理部２３１と、座標更新部２３２と、ソート部２３３と、判定部２３４と、ＡＥＬ分割部２３５と、ＡＥＬ結合部２３６と、ピクセル生成部２３７とを含む。なお、「ＡＥＬ」はアクティブエッジリスト（Ａｃｔｉｖｅ  Ｅｄｇｅ  Ｌｉｓｔ）を意味し、説明を簡略化するために以下同様に「ＡＥＬ」と記す。
【００１６】
ＰＤＬ解釈部２１０は、ＰＤＬデータの解釈を行う。中間データ生成部２２０は、ＰＤＬデータの解釈結果に基づいて中間データを生成する。画像生成部２３０は、中間データ生成部２２０によって生成された中間データを入力としてビットマップ画像データを生成する。  
【００１７】
ＡＥＬ管理部２３１は、エッジ情報が記憶されるＡＥＬを用いて、走査ラインと交差するエッジを管理する。座標更新部２３２は、ＡＥＬで管理されるエッジの座標を更新する。ソート部２３３はＡＥＬで管理されるエッジをソートする。判定部２３４は、ＡＥＬで管理されるエッジ情報の数Ｃが、閾値Ｎ以上となるか否かを判定する。ＡＥＬ分割部２３５はＡＥＬを分割する。ＡＥＬ結合部２３６はＡＥＬを結合する。ピクセル生成部２３７は、ＡＥＬを入力としてビットマップ画像データを構成するピクセルを生成する。
【００１８】
図３は、本実施形態におけるレンダリング手順例を示すフローチャートである。図３に示されるフローチャートの処理は、ＣＰＵ１０１またはＡＳＩＣ１０５がレンダリングプログラム２００のプログラムコードを読み出して実行することにより行われる。あるいはまた、図３に示されるフローチャートの処理は、ＣＰＵ１０１とＡＳＩＣ１０５が協働して動作することにより実現されてもよい。以下の各記号Ｓは、フローチャートにおけるステップであることを意味する。これらは図３以降のフローチャートについても同様である。
【００１９】
Ｓ３０１において、ＰＤＬ解釈部２１０は、情報処理装置１０から受信したＰＤＬデータの解釈を行う。本実施形態のＰＤＬデータには、ページ記述型言語（Ｐａｇｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ）であるＰＤＦデータやＸＰＳデータなどを適用することができる。本実施形態のＰＤＬデータは、オブジェクトを含む。オブジェクトは、印刷データにおけるページの任意の位置に文字、図形、画像などを描画する描画命令によって構成される。
【００２０】
Ｓ３０２において、中間データ生成部２２０は、ＰＤＬデータの解釈結果に基づいて中間データを生成する。
【００２１】
図４（ａ）はオブジェクト例を表す模式図である。  
【００２２】
図４（ａ）に示されるオブジェクトは、４つのエッジＥａ，Ｅｂ，Ｅｃ，Ｅｄから構成される多角形オブジェクトである。
【００２３】
図４（ｂ）はリストの内容例を表す模式図である。  
【００２４】
図４（ａ）に示される印刷データの座標系における走査方向（横軸）をＸ軸、走査方向と直交する方向（縦軸）をＹ軸としたとき、エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄはそれぞれ座標値の集合として表すことができる。Ｙ座標値の絶対値が最も小さい頂点がエッジの始点（以下「エッジ始点」と記す）に、Ｙ座標値の絶対値が最も大きい頂点がエッジの終点（以下「エッジ終点」と記す）に設定される。例えば、エッジＥａのエッジ始点は座標（Ｘ１，Ｙ１）であり、エッジ終点は座標（Ｘ２，Ｙ２）である。そして、エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄが、それぞれのエッジ始点のＹ座標値に従ってソートされ、ソートされたエッジＥａ，Ｅｂ，Ｅｃ，Ｅｄに対応するエッジ情報が、図４（ｂ）に示されるリストに記憶される。
【００２５】
また、エッジ始点が同じ複数のエッジが存在する場合、これら複数のエッジに対応するエッジ情報はポインタで連結される。例えば、エッジＥａ，Ｅｂのエッジ始点はそれぞれ（Ｘ１，Ｙ１）であり、エッジＥａのエッジ情報４０２とエッジＥｂのエッジ情報４０３とがポインタで連結されて、Ｙ１に対応するリスト４０１のセルに記憶される。  
【００２６】
エッジＥｃのエッジ始点は（Ｘ２，Ｙ２）であり、エッジＥｃのエッジ情報がＹ２に対応するリスト４０１のセルに記憶され、エッジＥｄのエッジ始点は（Ｘ３，Ｙ３）であり、エッジＥｄのエッジ情報がＹ３に対応するリスト４０１のセルに記憶される。  
【００２７】
なお、印刷データにおける走査ラインは、図４（ａ）において破線で表されている。このように、本実施形態の中間データは、エッジ始点のＹ座標値に対応するセルにそれぞれのエッジ情報が記憶されるリスト形式となっている。  
【００２８】
また、図４（ａ）において、エッジＥａ，Ｅｃは開始エッジであり、エッジＥｂ，Ｅｄは終了エッジである。本実施形態では、オブジェクトのエッジは開始エッジと終了エッジとの対で構成され、開始エッジＥａ，Ｅｃに対応するエッジ情報と、終了エッジＥｂ，Ｅｄに対応するエッジ情報がそれぞれ対応付けられてリスト４０１のセルに記憶される。
【００２９】
図４（ｃ）はエッジ情報の内容例を表す模式図である。  
【００３０】
本実施形態のエッジ情報は、エッジ始点と、エッジ始点からの変位量とによって表される。すなわち、エッジ始点のＸ座標値４０４およびＹ座標値４０５と、走査ラインあたりの変位量を示すエッジ傾き４０６と、エッジと走査ラインとの交差数を示すエッジ高さ４０７とを含む。図４（ｃ）では、開始座標点が（８０、１２０）、傾きが０．５、高さが２４のエッジのエッジ情報の一例が示されている。以上説明した通り、本実施形態ではリストと、当該リストに記憶されるエッジ情報との全体が中間データに相当する。
【００３１】
Ｓ３０３において、画像生成部２３０は、中間データ生成部２２０によって生成された中間データを入力としてビットマップ画像データを生成する。ビットマップ画像データの生成において、画像生成部２３０は、各モジュール（ＡＥＬ管理部２３１〜ピクセル生成部２３７）が協調して動作を行えるようにシーケンスの制御も行う。
【００３２】
図５は、本実施形態における画像生成（Ｓ３０３）の詳細手順例を示すフローチャートである。以下、図５のフローチャートを参照して、主にＡＥＬの生成手順およびＡＥＬの更新手順について説明する。
【００３３】
Ｓ５０１において、ＡＥＬ管理部２３１は、走査ラインと交差するエッジを管理するために用いられるＡＥＬを生成する。このとき、走査ラインのＹ座標値はＹ＝０、つまり走査ラインが印刷データの最上部に位置している状態である。本実施形態において、ＡＥＬとは、中間データからビットマップ画像データに展開される際に行われる走査変換において、走査変換の対象となるエッジが記憶されるリストを示す。以下、図６（ａ）〜（ｃ）を参照して、本実施形態のＡＥＬについて説明する。
【００３４】
図６（ａ）はオブジェクト例を表す模式図である。  
【００３５】
図６（ａ）に示されるオブジェクトは、４つのエッジＥａ，Ｅｂ，Ｅｃ，Ｅｄから構成される多角形オブジェクトである。
【００３６】
図６（ｂ）はＡＥＬの内容例を表す模式図である。  
【００３７】
ＡＥＬ６１０は、走査ラインのＹ座標がＹ＝０のときに生成されたＡＥＬの内容例を表している。ＡＥＬ６１０は、Ｈｅａｄ６１１を先頭とし、Ｔａｉl６１２を最後尾とした、双方向リスト形式となっている。走査ラインのＹ座標がＹ＝０のときに走査ライン上にエッジは存在しない。そのため、ＡＥＬ６１０にはエッジ情報が記憶されない。
【００３８】
ＡＥＬ６２０は、走査ラインのＹ座標がＹ＝１のときに生成されたＡＥＬの内容例を表している。エッジＥａ，Ｅｂは、それぞれ座標値（Ｘ１，Ｙ１）をエッジ開始点とするエッジであり、エッジＥａのエッジ情報６２２，エッジＥｂのエッジ情報６２３がそれぞれリスト４０１からＡＥＬ６２０に読み込まれている。
【００３９】
ＡＥＬ６３０は、走査ラインのＹ座標がＹ＝２のときに生成されたＡＥＬの内容例を表している。エッジＥａは、座標値（Ｘ２，Ｙ２）を終了点とするエッジであり、エッジＥａのエッジ情報６２２がＡＥＬから削除されている。一方、エッジＥｃは、座標値（Ｘ２，Ｙ２）をエッジ開始点とするエッジであり、エッジＥｃのエッジ情報６３２がリスト４０１からＡＥＬ６３０に読み込まれている。なお、本実施形態において、エッジ情報はＸ座標が昇順となるようにＡＥＬに記憶されるため、エッジＥｃのエッジ情報６３２、エッジＥｂのエッジ情報６３３の順にＡＥＬ６３０に記憶されている。
【００４０】
ＡＥＬ６４０は、走査ラインのＹ座標がＹ＝３のときに生成されたＡＥＬの内容例を表している。エッジＥｂは、座標値（Ｘ３，Ｙ３）を終了点とするエッジであり、エッジＥｂのエッジ情報６３３がＡＥＬから削除されている。一方、エッジＥｄは、座標値（Ｘ３，Ｙ３）をエッジ開始点とするエッジであり、エッジＥｄのエッジ情報６４３がリスト４０１からＡＥＬ６４０に読み込まれている。
【００４１】
ＡＥＬ６５０は、走査ラインのＹ座標がＹ＝４のときに生成されたＡＥＬの内容例を表している。エッジＥｃ，Ｅｄは、それぞれ座標値（Ｘ４，Ｙ４）を終了点とするエッジであり、エッジＥｃのエッジ情報６４２、エッジＥｄのエッジ情報６４３がそれぞれＡＥＬから削除されている。この結果、ＡＥＬ６５０は、Ｈｅａｄ６５１を先頭とし、Ｔａｉl６５２を最後尾とした、エッジ情報を含まないＡＥＬとなっている。
【００４２】
図６（ｃ）は、エッジ情報の内容を表す模式図である。
【００４３】
図６（ｃ）では、エッジ開始点が（Ｘ０，Ｙ０）、傾きがＤ、高さがＮのエッジのエッジ情報の一例が示されている。本実施形態のＡＥＬは、走査ラインのＹ座標値をインクリメントすることに応じてＹ軸方向に移行されることから、このＡＥＬのエッジ情報が取り得るＹ座標値Ｙｃは、Ｙ０以上かつＹ＋Ｎ未満となる。また、このＡＥＬのエッジ情報が取り得るＸ座標値Ｘｃは、以下の式から導出される。  
【００４４】
【数１】
2019087163.tif 000003
【００４５】
Ｙ座標値がＹｃ＝Ｙ＋Ｎとなった場合、エッジが終端に到達したと判断され、当該エッジに対応するエッジ情報はＡＥＬから削除されることとなる。
【００４６】
再び図５のフローチャートに戻り、Ｓ５０２において、座標更新部２３２は、Ｓ５０１で生成されたＡＥＬを更新する。ＡＥＬ更新処理の詳細は後述する。
【００４７】
Ｓ５０３において、ピクセル生成部２３７は、Ｓ５０２で更新されたＡＥＬを入力としてピクセルを生成する。ピクセル生成部２３７で生成された各ピクセルは、ビットマップ画像データを構成する。Ｓ５０３のピクセル生成処理では、いずれのオブジェクトが前方に位置し、いずれのオブジェクトが後方に位置するかが特定され、このオブジェクト間の位置関係に基づいて描画対象となるオブジェクトが選択される。次いで、選択されたオブジェクトの塗り情報を生成するフィル生成処理と、オブジェクトを重ね合わせるコンポジット処理とが行われる。
【００４８】
Ｓ５０４において、画像生成部２３０は、全ての走査ラインについて処理が完了したか否かを判定する。全ての走査ラインについて処理が完了した場合（Ｓ５０４：ＹＥＳ）は再び図３のフローチャートに戻る。全ての走査ラインについてピクセル生成処理が完了していない場合（Ｓ５０４：ＮＯ）はＳ５０５に移行する。
【００４９】
Ｓ５０５において、画像生成部２３０は、Ｙ座標の座標値をインクリメントすることにより注目走査ラインを次の走査ラインに移行させる。
【００５０】
Ｓ５０６において、判定部２３４は、ＡＥＬに記憶されるエッジ情報の数Ｃが、閾値Ｎ以上となるか否かを判定する。Ｃ≧Ｎである場合（Ｓ５０６：ＹＥＳ）はＳ５０７に移行する。Ｃ＜Ｎである場合（Ｓ５０６：ＮＯ）はＳ５０８に移行する。
【００５１】
Ｓ５０７において、ＡＥＬ分割部２３５はＡＥＬを分割して、走査変換処理の対象となるエッジを複数のグループに分割する。ここで、ＡＥＬが分割される様子を図７〜図８を参照して説明する。
【００５２】
図７（ａ）はオブジェクト例を表す模式図である。  
【００５３】
図７（ａ）に示されるオブジェクトは、エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄで囲われる矩形オブジェクトおよびエッジＥｅ，Ｅｆ，Ｅｇで囲われる三角形オブジェクトである。
【００５４】
図７（ｂ）はＡＥＬの内容例を表す模式図である。  
【００５５】
ＡＥＬ７１０は、走査ラインのＹ座標がＹ＝１のときに生成されたＡＥＬの内容例を表しており、Ｅｂ，Ｅｄの順でエッジ情報がＡＥＬ７１０に記憶される。  
【００５６】
ＡＥＬ７２０は、走査ラインのＹ座標がＹ＝２のときに生成されたＡＥＬの内容例を表しており、Ｅｂ，Ｅｄ，Ｅｅ，Ｅｇの順でエッジ情報がＡＥＬ７２０に記憶される。  
【００５７】
ＡＥＬ７３０は、走査ラインのＹ座標がＹ＝３のときに生成されたＡＥＬの内容例を表しており、Ｅｂ，Ｅｄの順でエッジ情報がＡＥＬ７３０に記憶される。  
【００５８】
ＡＥＬ７４０は、走査ラインのＹ座標がＹ＝４のときに生成されたＡＥＬの内容例を表しており、ＡＥＬ７４０にはエッジ情報はＡＥＬ７４０に記憶されない。
【００５９】
図８（ａ）にはＡＥＬが分割される様子が示されており、分割対象となるＡＥＬ７２０に記憶されるエッジ情報の数ＣはＣ＝４である。例えば、閾値ＮがＮ＝４の場合、Ｃ≧Ｎとなるため（Ｓ５０６）、ＡＥＬ７２０はＡＥＬ８２０ａと、ＡＥＬ８２０ｂとに分割される。なお、以後の処理において、ＡＥＬに記憶されるエッジ情報の数ＣがＣ＜Ｎとならない限り、ＡＥＬは複数のＡＥＬに分割されたままとなる。
【００６０】
また、上記では所定の閾値を基準としてＡＥＬを分割するか否かを決定していた。実施形態はこれに限られず、印刷データにおけるページ幅を基準としてＡＥＬを分割するか否かを決定してもよい。例えば、ＡＥＬ７２０にはエッジＥｂ，Ｅｄ，Ｅｅ，Ｅｇのエッジ情報が記憶されているが、ページの境界７０１を中心として、エッジＥｂ，ＥｄのＸ座標値はいずれも左ページに位置しており、エッジＥｅ，ＥｇのＸ座標値はいずれも右ページに位置している。このとき、ページ幅を基準としてＡＥＬ７２０を分割する場合、Ｅｂ，Ｅｄの順で記憶されるＡＥＬと、Ｅｅ，Ｅｇの順で記憶されるＡＥＬとに分割することができる。
【００６１】
再び図５のフローチャートに戻り、Ｓ５０８において、ＡＥＬ結合部２３６はＡＥＬを結合して、走査変換処理の対象となるエッジを含む複数のグループを結合する。ここで、ＡＥＬが結合される様子を図８を参照して説明する。
【００６２】
図８（ｂ）にはＡＥＬが結合される様子が示されており、結合対象となるＡＥＬ７３０およびＡＥＬ７４０に記憶されるエッジ情報の数ＣはそれぞれＣ＝２，０である。例えば、閾値ＮがＮ＝４の場合、Ｃ＜Ｎとなるため（Ｓ５０６）、ＡＥＬ７３０とＡＥＬ７４０とは単一のＡＥＬ８５０に結合される。Ｓ５０７においてＡＥＬが分割され、または、Ｓ５０８においてＡＥＬが結合されると、再びＳ５０２に戻る。
【００６３】
次に、図９のフローチャートを参照して、本実施形態におけるＡＥＬの更新手順例の詳細について説明する。  
【００６４】
Ｓ９０１において、ＡＥＬ管理部２３１は、走査ラインとエッジとが新たに交差するようになった場合、当該エッジに対応するエッジ情報をＡＥＬに読み込む。
【００６５】
Ｓ９０２において、座標更新部２３２は、ＡＥＬに記憶される全てのエッジ情報を更新する。具体的には、上述した（式１）を用いて、現在の走査ラインに対応するエッジのＸ座標値が導出される。導出されたＸ座標値がエッジ終了点である場合、このエッジのエッジ情報がＡＥＬから削除される。
【００６６】
Ｓ９０３において、ＡＥＬ管理部２３１は、ＡＥＬが分割されているか否かを判定する。ＡＥＬが分割されている場合（Ｓ９０３：ＹＥＳ）はＳ９０４に移行する。ＡＥＬが分割されていない場合（Ｓ９０３：ＮＯ）はＳ９０６に移行する。
【００６７】
Ｓ９０４において、ＡＥＬ管理部２３１は、ページを跨ぐエッジが存在するか否かを判定する。ページを跨ぐエッジが存在する場合（Ｓ９０４：ＹＥＳ）はＳ９０５に移行する。ページを跨ぐエッジが存在しない場合（Ｓ９０４：ＮＯ）はＳ９０５をスキップしてＳ９０６に移行する。
【００６８】
Ｓ９０５において、ＡＥＬ管理部２３１は、ＡＥＬに記憶されるエッジ情報を他のＡＥＬに移動させる。ここで、図１０を参照して、ページを跨ぐエッジが存在する場合に、ＡＥＬに記憶されるエッジ情報を移動させる実施例について説明する。
【００６９】
図１０（ａ）はオブジェクト例を表す模式図である。  
【００７０】
図１０（ａ）に示されるオブジェクトは、エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄから構成される矩形オブジェクトおよびエッジＥｅ，Ｅｆ，Ｅｇから構成される三角形オブジェクトである。
【００７１】
図１０（ｂ）はＡＥＬの内容例を表す模式図である。
【００７２】
図１０（ｂ）では、Ｅｂ，Ｅｄ，Ｅｅ，Ｅｇの順でエッジ情報が記憶されていたＡＥＬが、エッジ情報の数ＣがＣ＝４であり、閾値ＮがＮ＝４であるものとして、分割されたＡＥＬ１０１０ａと１０１０ｂとが示されている。ＡＥＬ１０１０ａと１０１０ｂとは、走査ラインのＹ座標がＹ＝１のときに更新されたＡＥＬの内容例を表しており、Ｅｂ，ＥｄとＥｅ，Ｅｇとの順でエッジ情報がＡＥＬ１０１０ａと１０１０ｂとにそれぞれ記憶される。
【００７３】
図１０（ａ）に示される通り、入力データは左ページ１００１ａと、右ページ１００１ｂとに区画されている。走査ラインのＹ座標値がＹ＝１からＹ＝２に移行するに伴い、Ｙ＝１では右ページ１００１ｂに存在していたエッジＥｅが、Ｙ＝２では左ページ１００１ａに位置していることが分かる。このように、ＡＥＬ管理部２３１は、ページを跨ぐエッジが存在する場合、このページを跨ぐエッジＥｅのエッジ情報を、ＡＥＬ１０１０ｂからＡＥＬ１０１０ａに移動させる。  
【００７４】
ＡＥＬ１０２０ａと１０２０ｂとは、走査ラインのＹ座標がＹ＝２にインクリメントされることに応じて更新されたＡＥＬの内容例を表しており、それぞれＥｂ，Ｅｄ，ＥｅとＥｇの順でエッジ情報がＡＥＬ１０２０ａと１０２０ｂとにそれぞれ記憶される。つまり、図１０（ｂ）では、エッジ情報Ｅｅが移動された後のＡＥＬ１０２０ａ，１０２０ｂの内容例が示されている。なお、図１０（ａ）に示されるページ幅は、レンダリング装置１００の操作者が予め設定することができ、具体的には、印刷に用いられるプリント用紙の紙面幅に好適に設定される。
【００７５】
再び図９のフローチャートに戻り、Ｓ９０６において、ソート部２３３はＡＥＬに記憶されるエッジ情報をソートする。これは、いずれのオブジェクトが前方に位置し、いずれのオブジェクトが後方に位置するかを特定するために必要な処理であり、ＡＥＬが分割されている場合、分割された複数のＡＥＬそれぞれにエッジ情報のソートが行われる。
【００７６】
ここで、ＡＥＬに記憶されるエッジ情報がソートされる様子を、図１１を参照して説明する。  
【００７７】
図１１（ａ）はオブジェクト例を表す模式図である。  
【００７８】
図１１（ａ）に示されるオブジェクトは、エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄから構成される矩形オブジェクトおよびエッジＥｅ，Ｅｆ，Ｅｇから構成される三角形オブジェクトである。
【００７９】
図１１（ｂ）はＡＥＬの内容例を表す模式図である。  
【００８０】
ＡＥＬ１１１０は、走査ラインのＹ座標がＹ＝１のときに生成されたＡＥＬの内容例を表しており、Ｅｂ，Ｅｄ，Ｅｆ，Ｅｅの順でエッジ情報がＡＥＬ１１１０に記憶される。ＡＥＬ１１１０に記憶されるエッジ情報は、Ｘ座標値が昇順となるようにソートされている。  
【００８１】
ＡＥＬ１１２０は、走査ラインのＹ座標がＹ＝２のときに生成されたＡＥＬの内容例を表しており、Ｅｂ，Ｅｆ，Ｅｄ，Ｅｅの順でエッジ情報がＡＥＬ１１２０に記憶される。
【００８２】
これは、走査ラインがＹ＝１からＹ＝２に移行することに応じて、Ｘ座標値が昇順となるようにエッジ情報がソートされた結果、エッジＥｄとＥｆとの順番が入れ替わったためである。なお、エッジ情報のソート手法には、例えば一般的なクイックソートを適用することができる。もちろんクイックソート以外の手法を適用してもよい。
【００８３】
Ｓ９０７において、ＡＥＬ管理部２３１は、ＡＥＬが分割されているか否かを判定する。ＡＥＬが分割されている場合（Ｓ９０７：ＹＥＳ）はＳ９０８に移行する。ＡＥＬが分割されていない場合（Ｓ９０７：ＮＯ）はＳ９０８をスキップして本フローチャートを終了し、再び図５のフローチャートに戻る。
【００８４】
Ｓ９０８において、ＡＥＬ結合部２３６は、分割されているＡＥＬを結合する。ＡＥＬを結合する処理内容はＳ５０８と同じである。本実施形態では、走査ライン単位でエッジ情報がピクセル生成部２３７に入力される必要があるため、ピクセル生成（Ｓ５０３）の直前に、分割されたＡＥＬが再び単一のＡＥＬに結合される。Ｓ９０８が終了すると、本フローチャートを終了して再び図５のフローチャートに戻る。
【００８５】
図１２は、本実施形態におけるレンダリング手法を適用した場合の効果を説明する図である。図１２は、横軸をオブジェクト数、縦軸をレンダリング処理に要する計算時間としたグラフ例である。本実施形態では、エッジ情報のソート処理（Ｓ９０６）は、ｑｓｏｒｔを用いて実現されている。ソート処理の対象となるオブジェクト数をｎとした場合、ｑｓｏｒｔの理論上の性能は、ｎｌｏｇｎで表される。本実施形態のレンダリング手法では、このエッジ情報のソート処理の高速化が図られている。
【００８６】
具体的には、例えば、ある走査ラインと交差するオブジェクトがｎ個の場合（すなわち、エッジの数ＣがＣ＝２ｎの場合）、ｑｓｏｒｔを用いたソート処理に必要な処理時間は（２ｎ）ｌｏｇ（２ｎ）で表される。一方、本実施形態におけるレンダリング手法によれば、分割したそれぞれのＡＥＬに対してそれぞれソート処理が行われる。例えば、ＡＥＬを２つに分割した場合、走査ラインにおけるオブジェクトの個数は０．５ｎ個（すなわち、エッジの数ＣがＣ＝ｎ）であることから、それぞれのＡＥＬに記憶されるエッジ情報をソートするために必要な処理時間はｎ×ｌｏｇ（ｎ）で表される。そして、ＡＥＬ全体に記憶されるエッジ情報をソートするために必要な処理時間は２×ｎ×ｌｏｇ（ｎ）＝２ｎ×ｌｏｇ（ｎ）で表されることになる。
【００８７】
図１２のグラフでは、ＡＥＬを分割しない手法におけるオブジェクト数と処理時間との関係が実線で、ＡＥＬを分割する手法におけるオブジェクト数と処理時間との関係が破線で表されている。本実施形態におけるレンダリング手法を適用した場合、矢印１２０１が示す通り、ＡＥＬに記憶されるエッジ情報の数が多いほどレンダリングに必要な処理時間の低減効果を得ることができる。しかしながら、ＡＥＬに記憶されるエッジ情報の数が少ない場合、ＡＥＬを分割するメリットが少なくなり、場合によってはソート処理のオーバヘッドの影響により、レンダリングに必要な処理時間が増加してしまうことも考えられる。そのため、本実施形態のレンダリング手法によれば、ある閾値Ｎを基準として、ＡＥＬ記憶されるエッジ情報の数ＣがＣ＜Ｎとなる場合、ＡＥＬに記憶されるエッジ情報が結合される。
【００８８】
以上説明した通り、本実施形態のレンダリング手法によれば、ＡＥＬで管理されるエッジが複数のグループに分割され、管理対象となるエッジを、分割された複数のグループごとにソートする。そのため、印刷データに含まれるエッジの数が増加した場合であっても、走査変換におけるソート処理に必要な時間を短縮することができる。
【００８９】
［実施形態２］
実施形態１のレンダリング手法では、予め定められた所定の閾値や、印刷データのページ幅を基準にＡＥＬを分割していた。本実施形態では、ＡＥＬで管理されるエッジの数を基準として、ＡＥＬを分割するか否かを決定する実施例について説明する。なお、実施形態１と共通する部分については説明を簡略化ないし省略し、以下では本実施形態に特有な点を中心に説明する。
【００９０】
図１３は、本実施形態におけるＡＥＬの更新手順例の詳細を示すフローチャートである。本実施形態におけるＡＥＬの更新（Ｓ５０２）では、Ｓ１３０１の処理が実施形態１と相違する。エッジ情報の更新（Ｓ９０２）において、ＡＥＬに記憶されるエッジ情報が削除されることにより、分割されたＡＥＬに記憶されるそれぞれのエッジ情報の数に偏りが生じる場合がある。
【００９１】
そのため本実施形態では、Ｓ１３０１において、ＡＥＬ管理部２３１は、分割されたＡＥＬに記憶されるエッジ情報の数に偏りが生じているか否かを判定する。エッジ情報の数に偏りが生じている場合（Ｓ１３０１：ＹＥＳ）はＳ９０５に移行する。エッジ情報の数に偏りが生じていない場合（Ｓ１３０１：ＮＯ）はＳ９０５をスキップしてＳ９０６に移行する。
【００９２】
ここで、ＡＥＬに記憶されるエッジ情報の数に偏りが生じている様子を、図１４を参照して説明する。  
【００９３】
図１４（ａ）はオブジェクト例を表す模式図である。  
【００９４】
図１４（ａ）に示されるオブジェクトは、エッジＥａ，Ｅｂ，Ｅｃ，Ｅｄで囲われる矩形オブジェクト、エッジＥｅ，Ｅｆ，Ｅｇ，Ｅｈで囲われる矩形オブジェクトおよびエッジＥｉ，Ｅｊ，Ｅｋで囲われる三角形オブジェクトである。
【００９５】
図１４（ｂ）はＡＥＬの内容例を表す模式図である。  
【００９６】
ＡＥＬ１４１０ａと１４１０ｂとは、走査ラインのＹ座標がＹ＝１のときのＡＥＬの内容例を表している。ＡＥＬ１４１０ａ，１４１０ｂとは、エッジ情報の数ＣがＣ＝４であり、閾値ＮがＮ＝４であるものとして、Ｅｂ，Ｅｄ，Ｅｆ，Ｅｈ，Ｅｉ，Ｅｋの順でエッジ情報が記憶されていたＡＥＬが分割されたものである。
【００９７】
図１４（ａ）に示される通り、走査ラインのＹ座標値がＹ＝１からＹ＝２に移行するに伴い、Ｙ＝１ではＡＥＬ１４１０ｂに記憶されていたＥｉ，Ｅｋのエッジ情報が、Ｙ＝２ではＡＥＬ１４２０ｂから削除されていることが分かる。このように、エッジ情報の更新（Ｓ９０２）によって、ＡＥＬ１４２０ａに記憶されるエッジ情報の数ＣがＣ＝３、ＡＥＬ１４２０ｂに記憶されるエッジ情報の数ＣがＣ＝１となり、エッジ情報の数に偏りが生じている。
【００９８】
分割されたＡＥＬに記憶されるエッジの数に偏りが生じている場合（Ｓ１３０１：ＹＥＳ）、ＡＥＬ管理部２３１は、ＡＥＬに記憶されるエッジ情報を移動させる（Ｓ９０５）。図１４（ｂ）では、エッジ情報の数の偏りを平準化するために、ＡＥＬ１４２０ａに記憶されているＥｆのエッジ情報が、ＡＥＬ１４２０ｂに移動される。この結果、走査ラインのＹ座標値がＹ＝２のとき、Ｅｂ，Ｅｄの順でエッジ情報がＡＥＬ１４２０ｃに、Ｅｆ，Ｅｈの順でエッジ情報がＡＥＬ１４２０ｄに記憶される。
【００９９】
本実施形態では、分割されたＡＥＬに記憶されるエッジ情報の数がそれぞれ等しくなるようにエッジ情報の移動が行われたが、予め定められた値を基準にエッジ情報を移動させるか否かを判定してもよい。例えば、あるＡＥＬａ，ｂに記憶されるエッジ情報の数をそれぞれＮａ，Ｎｂとしたとき、｜Ｎａ−Ｎｂ｜の値が所定の値以上となった場合に、エッジ情報を移動させることもできる。また、本実施形態では２つのＡＥＬを２つに分割したが、３，４などの任意の数のＡＥＬに分割してもよい。
【０１００】
以上説明した通り、本実施形態のレンダリング手法によれば、ＡＥＬで管理されるエッジが複数のグループに分割され、管理対象となるエッジを、分割された複数のグループごとに平準化する。そのため、印刷データに含まれるエッジの数に偏りが生じた場合であっても、走査変換におけるソート処理に必要な時間を短縮することができる。
【０１０１】
［実施形態３］
実施形態１および実施形態２では、走査ライン上のエッジの数に応じてＡＥＬを分割するか否かを判定していた。本実施形態では、ページ幅に応じてＡＥＬの分割を行うか否かを切り替えることを特徴とする。具体的には、予め設定されているページ幅と予め定められた閾値とを比較し、ページ幅が閾値以上となる場合は当該ページに対応するＡＥＬの分割が行われ、ページ幅が閾値を下回る場合には分割が行われない。なお、このようなページ幅は、レンダリング装置１００の操作者が予め設定してもよいし、印刷ページに対して設定されるプリンタ用紙の紙面幅としてもよい。
【０１０２】
本実施形態のレンダリング手法によれば、ＡＥＬを分割した場合にソート処理のオーバヘッドが発生してしまう場合であっても、ＡＥＬの分割を行うか否かを切り替えることにより、走査変換におけるソート処理に必要な時間を短縮することができる。
【０１０３】
（その他の実施例）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【図１】
2019087163.tif 000004
【図２】
2019087163.tif 000005
【図３】
2019087163.tif 000006
【図４】
2019087163.tif 000007
【図５】
2019087163.tif 000008
【図６】
2019087163.tif 000009
【図７】
2019087163.tif 000010
【図８】
2019087163.tif 000011
【図９】
2019087163.tif 000012
【図１０】
2019087163.tif 000013
【図１１】
2019087163.tif 000014
【図１２】
2019087163.tif 000015
【図１３】
2019087163.tif 000016
【図１４】
2019087163.tif 000017