(57)【要約】【課題】  従来のRIPのエッジ処理は、エッジが垂直（X座標が不変）であっても、各Y座標でX座標の計算を行っていた。そのためエッジのX座標計算に不要な時間が掛かっているという第１の課題がある。また、エッジ開始とともにエッジ処理で使用するメモリを逐次確保し、終了とともにメモリを逐次解放することを行っていた。そのため、メモリ領域が離散的に使用されキャッシュ効率が悪いという第２の課題がある。【解決手段】  第１の課題を解決するために中間データからエッジを読み込むときに、エッジのX座標の変化量から垂直エッジか否かを判断し、垂直エッジと判断されたら、通常のエッジとは別にして管理する。第２の課題を解決するために中間データからエッジを読み込むときに、エッジのペアを検出する。エッジのペアを検出したら、エッジのペアの更新情報をまとめて一つの構造体で管理する。【選択図】  図７B
2012159963.tif 000002
【特許請求の範囲】
【請求項１】
各Y座標単位でオブジェクトのエッジを書き出して画像を形成する画像形成装置において、
中間データを読み込んで新規にエッジを追加するときに、オブジェクトの形状を成すエッジ対で該エッジY座標ごとに更新する情報を対でまとめるエッジ対更新ノードを確保する手段(S908)と、
オブジェクトの形状を成すエッジ対を検出して、エッジ対更新ノードにエッジ対のY座標ごとに更新するX座標の情報を格納するエッジ対まとめ手段(S907,S909,S915)と、
前記エッジ対更新ノードのエッジ終点座標格納部にエッジの終点Y座標を書き込む手段、(S910)と、
エッジがX軸方向に対して垂直であるか否かを判定する垂直判定手段(S912,S918)と、
前記垂直判定手段にて垂直と判定された場合にエッジが垂直であることを前記エッジ対更新ノードの垂直判定結果格納部を書き込む手段(S913,S919)と、
前記垂直判定手段にて該エッジ対のうち少なくとも一方のエッジが垂直と判定された場合に、主走査線数分用意された第一のリストのうち、該エッジ対の終点Y座標に対応するリストにエッジ対更新ノードを追加する第一のリスト追加手段(S922,S924)と、
前記垂直軌跡判定手段に該軌跡対のうち少なくとも一方が垂直ではないと判定された場合に、エッジ対更新ノードを第二のリストに追加する追加手段(S921,S923)と、
前記終点座標格納部に格納されているY座標が一致した場合に、エッジ対更新ノードを解放する手段(S1002,S1008,S1009)と、
各Y座標でエッジのX座標を更新するときに、前記第二のリストに登録されたエッジ対更新ノードからエッジが垂直か、否かを判定する垂直判定手段(S1005)と、
前記垂直判定手段にて、垂直ではないと判定されたエッジのX座標のみを更新するX座標更新手段(S1006)と、
前記主走査線数分用意された第一のリストのうち、現在注目しているY座標に対応するリストから前記エッジ対更新ノードを解放する手段(S1011)
を備えることを特徴とする画像形成装置。
【請求項２】
前記エッジ対まとめ手段は、紙面に対するオブジェクトの重ね合わせの順番を元にエッジ対を検出することを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記垂直判定手段は、前記エッジ対更新ノードからエッジのY座標毎のX座標の変化量を抽出して、始点Y座標から終点Y座標まで変化量がゼロの場合に垂直と判定することを特徴とする請求項１に記載の画像形成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリンタなどの画像形成装置における印刷システムおよび印刷システムの処理方法に関係するものである。詳しくは、印刷データに基づいた画像データを形成するRIP(Raster Image Processor)処理に関するものである。
【背景技術】
【０００２】
従来、プリンタで画像の出力を行なうためにPDL(Page Description Language)で記述されたプリントデータが使用されている。プリンタでは、PDLで記述されたプリントデータを解釈してRIPが受け取れる中間データへの変換を行い、RIP処理で中間データを元に画像を生成し、出力を行なっている。PDLで形状が矩形のオブジェクトの描画命令を含む場合、中間データの指示に従ってRIPのエッジ処理では、垂直なエッジを書き出すことがある。垂直なエッジを書き出す場合、X座標に変化が無いためY座標ごとにX座標の計算を行なう必要が無く、X座標の計算に掛かる時間を無駄にしていた。この問題に対して、特許文献１では、オブジェクトの輪郭を成すエッジのペアが矩形となるオブジェクトを判別して、矩形となるオブジェクトに対してエッジ処理を始点Y座標以降終点Y座標まで計算を回避することでRIP処理の効率化を行なっていた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開2008-117149号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら上述した特許文献１では、計算を回避して高速化する対象が矩形のエッジに限定されている。そのため片側のエッジが垂直で、残る一方のエッジが垂直でない（例えば直角三角形など）場合、特許文献１のエッジ処理の高速化が適用できないという課題がある。またエッジ処理では、中間データからのエッジ書き出しとともにエッジ座標の計算に使用するメモリを逐次確保し、エッジの書き終わりで確保したメモリを逐次解放することを行なうため、エッジ処理で使用するメモリ領域が離散的に確保されてしまうことがある。そのため、CPU(Central Processing Unit)キャッシュのキャッシュヒット率が低下しメモリアクセスに伴う処理に多くの時間を要してしまうという課題がある。
【課題を解決するための手段】
【０００５】
各Y座標単位でオブジェクトのエッジを書き出して画像を形成する画像形成装置において、
中間データを読み込んで新規にエッジを追加するときに、オブジェクトの形状を成すエッジ対で該エッジY座標ごとに更新する情報を対でまとめるエッジ対更新ノードを確保する手段(S908)と、
オブジェクトの形状を成すエッジ対を検出して、エッジ対更新ノードにエッジ対のY座標ごとに更新するX座標の情報を格納するエッジ対まとめ手段(S907,S909,S915)と、
前記エッジ対更新ノードのエッジ終点座標格納部にエッジの終点Y座標を書き込む手段、(S910)と、
エッジがX軸方向に対して垂直であるか否かを判定する垂直判定手段(S912,S918)と、
前記垂直判定手段にて垂直と判定された場合にエッジが垂直であることを前記エッジ対更新ノードの垂直判定結果格納部を書き込む手段(S913,S919)と、
前記垂直判定手段にて該エッジ対のうち少なくとも一方のエッジが垂直と判定された場合に、主走査線数分用意された第一のリストのうち、該エッジ対の終点Y座標に対応するリストにエッジ対更新ノードを追加する第一のリスト追加手段(S922,S924)と、
前記垂直軌跡判定手段に該軌跡対のうち少なくとも一方が垂直ではないと判定された場合に、エッジ対更新ノードを第二のリストに追加する追加手段(S921,S923)と、
前記終点座標格納部に格納されているY座標が一致した場合に、エッジ対更新ノードを解放する手段(S1002,S1008,S1009)と、
各Y座標でエッジのX座標を更新するときに、前記第二のリストに登録されたエッジ対更新ノードからエッジが垂直か、否かを判定する垂直判定手段(S1005)と、
前記垂直判定手段にて、垂直ではないと判定されたエッジのX座標のみを更新するX座標更新手段(S1006)と、
前記主走査線数分用意された第一のリストのうち、現在注目しているY座標に対応するリストから前記エッジ対更新ノードを解放する手段(S1011)
を備えることを特徴とする画像形成装置。
【発明の効果】
【０００６】
RIP処理部のエッジ処理にて垂直なエッジに対する座標計算の手間が省ける。またオブジェクトの輪郭をなすエッジのペアで使用する情報を１つにまとめることでキャッシュのヒット率が向上する。そのためRIP処理の高速になり、プリント処理をより効率的にを行なうことができる。
【図面の簡単な説明】
【０００７】
【図１】プリントシステムの概要を示したブロック図
【図２】プリントコントローラの概要を示したブロック図
【図３】RIP処理の概要を示した図
【図４】従来のエッジ処理で使用するデータのデータ構造の一例を示した図
【図５Ａ】紙面上に書き出されたエッジの一例を示した図
【図５Ｂ】従来のエッジ処理におけるデータ同士の関係を示した図
【図６】エッジのペアをまとめて管理するときのデータ構造の一例を示した図
【図７Ａ】紙面上に書き出されたエッジの一例を示した図
【図７Ｂ】エッジのペアをまとめて管理するときのエッジ処理の概要を示した図
【図８】エッジ処理の概要を示したフローチャート
【図９】エッジ追加処理を示したフローチャート
【図１０】エッジ更新処理を示したフローチャート
【発明を実施するための形態】
【０００８】
以下、本発明を実施するための最良の形態について図面を用いて説明する。
【０００９】
図１は、本発明に適用される印刷システムの一例を示している。
【００１０】
印刷システムは、ホストPC(Personal Computer)101、LAN(Local Area Network)102、プリンタ103で構成されている。ユーザーは、ホストPC101からLAN102経由して印刷指示をプリンタ103に通知する。プリンタ103はネットワークI/F(InterFace)104とプリントコントローラ105及びプリントエンジン106で構成されている。LAN102経由でホストPC101から通知された印刷指示は、ネットワークI/F104で受け付けられ、プリントコントローラ105に渡される。プリントコントローラ105では、印刷指示に従って画像データを形成し、その画像データをプリントエンジン106に渡す。プリントエンジン106は、画像データを元に紙媒体に印字出力を行なう。
【００１１】
図２は、プリントコントローラ105の内部構造の一例を示している。
【００１２】
プリントコントローラ105は、PDL解釈処理部201、中間データ格納部202、RIP(Raster Image Processor)処理部203、画像データ格納部204で構成されている。ネットワークI/F104で受け取った印刷指示は、プリントコントローラの内部のPDL()解釈処理部201に渡される。PDL解釈処理部201では、印刷指示を従って中間データの生成の行ない、中間データ格納部202に格納する。PDL解析処理部が１ページ分の印刷指示を中間データに変換し中間データ格納部202に格納すると、RIP処理部203は、中間データ格納部202に格納された中間データに基づい画像生成処理を行なう。RIP処理部203が生成した画像データは、画像データ格納部204に格納される。RIP処理部が画像生成処理を終了させると、プリントエンジン処理部106は、画像データ格納部204から画像データの読み込みを行い、印字処理を行なう。
【００１３】
図３は、RIP処理部204の内部構造の一例を示している。
【００１４】
RIP処理部204は、エッジ処理部301、レベル処理部302、フィル処理部303、コンポジット処理部304で構成されている。エッジ処理部301は、中間データを読み込み各Ｙ座標単位でオブジェクトのエッジ（輪郭）の座標を計算し、エッジで区切られる区間であるスパンをレベル処理部302に送信する。レベル処理部302では、エッジ処理301から受信したスパンを元に、スパン同士が紙面に対して正しいレベル（順番）で重なるように整列処理を行なう。レベル処理部302にて整列処理が済みのスパンは、フィル処理部303へと送信される。フィル処理部303は、レベル処理部302から受信した各スパンに対してフィル（色情報の割り当て）処理を行なう。フィル処理部303にてフィル処理済みのスパンは、コンポジット処理304に送信される。コンポジット処理部304ではフィル処理部303から受信したスパンを構成する一つ一つのピクセルに対してコンポジット（合成）処理を行なう。コンポジット処理の具体的な方法としては、ROP(Raster OPerator)及びαブレンドの２種類がある。ROPとは、重なり合うスパンのピクセル同士の各色値に対して論理演算を行なうことで、出力するピクセルを計算する方法である。αブレンドとは、重なり合うスパンのピクセル同士の色値を中間データから指定された一定の比率（αチャネル）に従って配合する方法である。コンポジット処理部にて計算された出力ピクセルは、画像データ格納部205に送信され格納される。
【００１５】
図４は、エッジ処理部で使用するエッジ情報を管理するデータ構造体の一例を示してい。る。
【００１６】
401はエッジノードと呼ばれるデータ構造である。エッジノード401には、エッジのX座標402及びエッジの元となるオブジェクトが紙面に対してどの順番に来るべきものなのかを示すレベル番号403及び、エッジリスト（後述）を構成するための次ポインタ404及び手前ポインタ405で構成されている。406は、エッジ更新ノードと呼ばれ、各Y座標にエッジノードに格納されているX座標を更新するために必要な情報を保持している。407は、X座標の更新情報である。各Y座標のX座標を計算するための情報が格納されている。具体的に格納される情報としては、次のY座標を+1したときのX座標の差分やエッジを形成する直線の方程式に関する情報などが上げられる。408は、エッジの終点情報でエッジの終点Y座標がどこであるかを示す情報を格納している。409は、エッジノードポインタでエッジ更新ノードと一対一に対応するエッジノードをリンクしているポインタである。410はエッジ更新ノードポインタでエッジ更新リスト（後述）を構成するためのポインタである。
【００１７】
図5Aでは、紙面上の座標空間に書き出されたエッジの様子を示している。図5Ａは、Ｘが主走査方向でＹが副走査方向を示していて、エッジe1 501とe1' 504及びエッジe2 502とe2' 503がそれぞれオブジェクトの輪郭を成すペアとなっている。これら4本のエッジは、共にY=y0がエッジの始点となっており、Y=y2が終点となっている。
【００１８】
図5Bは、図5AにおけるY=y1におけるエッジに伴うリンク構造を示している。505はエッジリストと呼ばれるエッジノードをリンクして形成するリストである。エッジリスト505では、エッジノードの次ポインタ404及び手前ポインタ405を使った双方向のリスト構造で、エッジの座標をX方向に正しい順番で管理するために、X座標に対して昇順にエッジノードがリンクされている。X座標を更新することによって、エッジリストに並ぶX座標の順番に変更が発生したときに、次ポインタ404及び手前ポインタ405を使ってエッジリストにリンクされているエッジノードの順番を入れ替えて整列し直す。現在注目しているエッジノードを基準にして、次ポインタ404の先にあるエッジノードは、X座標が同じか、それより大きい値のエッジノードとしている。
【００１９】
一方で手前ポインタ405の先にあるエッジノードは、X座標が同じかあれより小さい値のエッジノードとしている。そのため、エッジリスト505では、X座標の昇順にe1のエッジノード506、e2のエッジノード507、e2'のエッジノード508、e1'のエッジノード509の順番にリンクされている。510は、エッジ更新リストと呼ばれているエッジ更新ノードをリンクして形成するリストである。エッジ処理部301は、処理すべきY座標が+1進むごとにエッジ更新リスト510へのポインタ511からリンクされているエッジ更新ノードを参照し、各エッジノードのX座標を計算して更新していく。
【００２０】
本図によればエッジ更新リストはエッジ更新ノードe1のエッジ更新ノード512、e2のエッジ更新ノード513、e2'のエッジ更新ノード514、e1'のエッジ更新ノードの順番にリンクされている。そのためe1のエッジノード506、e2のエッジノード507、e2'のエッジノード508、e1'のエッジノード509の順番でX座標が更新される。エッジノード及びエッジ更新ノードは、エッジ処理部301が中間データから新規にエッジを展開するタイミングでメモリ上に確保され、エッジが終点まで達したときにメモリ上から解放される。
【００２１】
図６は、オブジェクトの輪郭を成すペアを成す２つのエッジのエッジ更新ノードをひとつにまとめた場合のエッジ更新ノードの一例を示している。601は、エッジ更新ノードである。603及び604は、エッジノードのX座標を更新するためのX座標の更新情報が格納されていて、更新情報として格納される内容は、それぞれ407と同じあでる。604及び605は、それぞれエッジノードへのポインタである。606は、エッジ種別判別フラグで垂直エッジ（後述）か、それ以外のエッジかを示すフラグ情報である。エッジ種別判別フラグは、垂直エッジの場合0b1、垂直ではないエッジの場合0b0とする。するとエッジ種別判別フラグは、エッジノードポインタ604にリンクされているエッジノード,及びエッジノードポインタ605にリンクされているエッジノードそれぞれに1bitずつで最低2bitあれば表現することが可能となっている。
【００２２】
607は、垂直エッジ更新リスト（後述）を構成するためのポインタである。608は、垂直ではないエッジでエッジ更新リストを構成するためのポインタである。609は、エッジの終点情報でエッジの終点Y座標がどこであるかを示す情報が格納されている。このように２つのエッジのエッジ更新ノードをひとまとめにすることで、メモリのキャッシュ効率を改善させることができる。また、オブジェクトの輪郭のペアを成す２つのエッジは、始点と終点のY座標が一致し、エッジ更新ノードをメモリ上に確保するタイミング及びメモリ上から解放するタイミングが一致する。そのためエッジ更新ノードに伴うメモリ管理の観点からも利便性が良いと考えられる。
【００２３】
図7Aでは、紙面上の座標空間に書き出されたエッジの様子を示している。図7Ａは、Ｘが主走査方向でＹが副走査方向を示していて、エッジe1 701とe1' 704、エッジe2 702とe2' 703及びエッジe3 705とe3' 706がそれぞれオブジェクトの輪郭を成すペアとなっている。これら6本のエッジは、共にY=y0がエッジの始点となっており、Y=y2が終点となっている。またエッジe2 702、e3 705及びe3' 706は、X軸に対しての垂直に展開されたエッジであり、このようなエッジを特別に垂直エッジと呼ぶ。垂直エッジは、X座標の変化が無いため、各Y座標に対してX座標を計算して更新する処理を必要としない。そして、垂直エッジは、エッジの始点にてX座標を特定する処理と、終点にてエッジノードとエッジ更新ノードをメモリから解放するのみを必要するという特徴がある。
【００２４】
図7Bは、図7AにおけるY=y1におけるエッジに伴うリンク構造を示している。707はエッジリストであり、前述のエッジリスト505と同様の役割をもっている。そのため、エッジリスト707では、X座標の昇順にe1のエッジノード708、e2のエッジノード709、e2'のエッジノード710、e2のエッジノード711、e3のエッジノード712、及びe3'のエッジノード713の順番にリンクしている。715は、エッジ更新リストである。エッジ更新リスト715は、エッジノード601のエッジ更新ノードポインタ608を用いてリンクされている。エッジ更新リスト715にリンクされているエッジ更新ノードは、ペアのエッジのうち少なくとも一方のエッジが垂直エッジではないエッジのエッジノードをもつエッジ更新ノードである。図7Aにおいてエッジe1 701、エッジe2' 703及びエッジe1 704が垂直エッジではない。そのため、エッジ更新リストには、e1とe1'のエッジ更新ノード716及びe2とe2'のエッジ更新ノード717がリンクされている。718は、垂直エッジ更新リスト管理テーブルである。垂直エッジ管理テーブル718には、各Y座標に終点となる垂直エッジをリンクしている垂直エッジリスト719へのポインタが格納されている。
【００２５】
エッジ処理部301は、垂直エッジ管理テーブルから垂直エッジリストへアクセスし、垂直エッジのエッジノード及びエッジ更新ノードをメモリ上から解放することを行なう。なお垂直エッジ更新リストは、エッジ更新ノード601の垂直エッジ更新ポインタ607でリンクさせることで構成される。垂直エッジ更新リスト719にリンクされるエッジ更新ノード601は、ペアのエッジのうち少なくとも一方のエッジが垂直エッジのエッジノードをもつエッジ更新ノードである。そのため、垂直エッジ管理テーブルのY=y2に該当する垂直エッジリストには、エッジe2とe2'のエッジ更新ノード717及びエッジe3とe3'のエッジ更新ノード720がリンクされている。
【００２６】
図8はエッジ処理部301で行なう概要を示したフローチャートである。S801でエッジ処理部301は、エッジ処理の終了を示すPageEndフラグをFalseで初期化。S802でエッジ処理部301は、Y=0からエッジ処理を行なったY座標をカウントするカウンタcntYを0で初期化する。S803はループ制御で、PageEndにFalseが格納されている間S804からS811までの処理の繰り返しを制御している。S804でエッジ処理部301は、中間データを読み込み、中間データに記載されている指示内容を解釈する。S805でエッジ処理部301は、指示内容がエッジ書き出しであればS806、指示内容がページ終了であればS810へと処理を進める。S806でエッジ処理部301は、エッジ追加処理（後述）を行なう。
【００２７】
S807でエッジ処理部301は、エッジ更新処理(後述)を行なう。S808でエッジ処理部301は、エッジリストから昇順に整列されている各エッジノードを読み込み、各エッジノードが保持するX座標の差からスパンの計算を行なうい、スパンとレベル番号をレベル処理部302へ送信を行なう。S809でエッジ処理部301は、CntYを+1インクリメントする。S810でエッジ処理部301は、PageEndフラグにTRUEを格納する。PageEndフラグにTRUEが格納されると、エッジ処理部301はS803のループから抜け、処理を終了する。
【００２８】
図９は、エッジ処理部301が中間データを読み込んでエッジを追加するエッジ追加処理を示したフローチャートでS806の詳細に該当するものある。S901でエッジ処理部は、現在注目しているY座標にて追加されるエッジデータの合計サイズEdgeTotalを取得する。ここでエッジデータとは、中間データからエッジノード及びエッジ更新ノードに書き込むべきデータを指している。S902でエッジ処理部301は、現在注目しているY座標にて現在までに読み込み済みのエッジに関するデータEdgeSizeに0を書き込み初期化する。S903はループ制御で、EdgeSizeがEdgeTotalに達するまでS904からS925までの処理の繰返しを制御している。S904でエッジ処理301は中間データから１つのエッジに関するデータの読み込みを行なう。S905でエッジ処理部301は、エッジノードをメモリから生成する。S906でエッジ処理部S301は、中間データから読み込んだエッジデータからエッジノードにレベル番号とエッジの始点X座標をエッジノードへコピーを行なう。
【００２９】
S906でエッジ処理部301は、レベル番号をインデックス値として、EdgePairTabに格納されている値を参照し、NULLだった場合S907へ処理を進め、NULL以外だった場合、S914へ処理を進める。EdgePairTabは、レベル番号をインデックス値として、各要素にレベル番号に合うオブジェクトの輪郭を成すエッジペアのエッジ更新ノードのアドレスを格納することで、エッジのペアを検出するために使用するテーブルである。インデックス値にレベル番号を使用する理由は、少なくとも同一のY座標上では、どのオブジェクトも紙面に対する順番（レベル）は異なるため、レベレベルを示すレベル番号がオブジェクト毎に異なることが保証される。そのため、同一のY座標上で、オブジェクトの輪郭を成すエッジのペアをレベル番号から検出することが可能だからである。EdgePairTabは、各要素に初期値としてNULLておく。NULLが格納されている場合、そのレベル番号に該当するエッジデータは、まだ１回も中間データから読み出されていないことを意味している。
【００３０】
一方でNULL以外の値が格納されている場合、その値はエッジ更新ノードのアドレスを示していて、既に一回は、中間データから該当するレベル番号のエッジが読み出されていることを意味している。前述の通り同一のY座標上でS907のタイミングでEdgePairTabの同じレベル番号に該当する要素を参照する回数は、２回しかない。従って、EdgePairTabの要素を参照し、NULL以外が格納されている場合は、エッジのペアを成す片側のエッジが既に中間データから読み出されていることを意味している。S908でエッジ処理部301は、エッジ更新ノードをメモリから生成する。S909でエッジ処理部301は、EdgePairTabの該当するレベル番号の要素にエッジ更新ノードのアドレスの書き込みを行なう。S910でエッジ処理部301は、中間データから取得したX座標更新情報をX座標更新情報[0] 602、エッジの終点Y座標をエッジの終点情報609にコピーする。S911でエッジ処理部301は、エッジノードのアドレスをエッジノードポインタ[0] 604に書き込み、エッジノードとエッジ更新ノードのリンクを行なう。
【００３１】
S912でエッジ処理部301は、エッジが垂直エッジか否かを判定する。垂直エッジと判定された場合S913へと処理を進め、垂直エッジではないと判定された場合、S914へと処理を進める。S912でエッジ処理部が行なう垂直エッジか否か判定は、X座標更新情報[0]とエッジの終点情報609を参照して、始点Y座標から終点YまでX座標の変化（進み幅ΔX）がゼロか否かを判定することで行なわれる。変化が無いと判定できた場合が垂直エッジで、変化があると判定された場合、垂直エッジでは無いこととしている。S913でエッジ処理部301は、エッジ種別判別フラグ606の1bit目に垂直エッジであることを示す0b1を書き込む。S914でエッジ処理部301は、現在のエッジ追加追加処理で中間データから読み込んだエッジデータのデータサイズEdgeDataをEdgeSizeに加算する。S915でエッジ処理部301は、EdgePairTabからエッジ更新ノードのアドレスを取得する。S916でエッジ処理部301は、アドレスを特定したエッジ更新ノードに中間データから取得したX座標更新情報をX座標更新情報[1] 603をコピーする。
【００３２】
S917でエッジ処理部301は、エッジノードのアドレスをエッジノードポインタ[1] 605に書き込み、エッジノードとエッジ更新ノードのリンクを行なう。S918でエッジ処理部301は、エッジが垂直エッジか否かを判定し、垂直エッジと判定された場合にS919へと処理を進め、垂直エッジではないと判定された場合にS920へと処理を進める。垂直エッジか否かの判定方法は、S912と同様である。S919でエッジ処理部301は、エッジ種別判別フラグ606の2bit目に0b1を書き込む。S920でエッジ処理部301は、エッジ種別判別フラグの値が0b10か0b01の場合にS921、0b00の場合にS923、0b11の場合にS924へと処理を進める。S921でエッジ処理部301は、エッジ更新リストにエッジ更新ノードの追加を行なう。S922でエッジ処理部301は、エッジ終端情報609を参照して、エッジの終点Y座標を確認して、垂直エッジ管理テーブルで該当するY座標の垂直エッジリストにエッジ更新ノードの追加を行なう。S923はS921とS924はS922と同様のため省略する。S925でエッジリストにペアとなる２つのエッジノードをそれぞれ追加する。S926でエッジ処理部301は、EdgePairTabの該当するレベル番号の要素をNULLで初期化する。
【００３３】
図10は、エッジ処理部301がエッジのX座標を更新するエッジ追加処理を示したフローチャートでS807の詳細に該当するものある。S1001は、ループ制御でエッジ処理部301がエッジ更新リストにリンクされているエッジ更新ノードをすべて参照し終えるまでS1002からS1010の処理を繰り返す。S1002でエッジ処理部301は、エッジ更新ノードのエッジの終点情報609を参照して、エッジが現在注目しているY座標にて終点となるか、否かを判定する。S1002でエッジ処理部は、エッジが終点Y座標に達していないと判定した場合にS1003、終点Y座標に達していると判定した場合にS1008に処理を進める。S1003でエッジ処理部301は、カウンタcntを0で初期化する。
【００３４】
S1004は、ループ制御でcntの値が2以上になるまでS1005とS1006の処理を繰り返す。S1005でエッジ処理部301は、エッジ種別判別フラグ606のcnt bit目が0b0か0b1かを判定する。S1005でエッジ処理部301が0b0と判定した場合にS1006、0b1と判別した場合にS1007へと処理を進める。S1006でエッジ処理部301は、エッジ更新ノードのエッジ[cnt]のX座標更新情報を元にエッジノード[cnt]へのエッジノードポインタ604/605から参照されるエッジノードのX座標402を更新する。S1007でエッジ処理部301は、cntを+1インクリメントする。S1008でエッジ処理部301は、エッジ種別判別フラグ606の値を参照し、その値が0b11の場合S1009、0b11以外の場合ループの開始である。S1001に処理を進める。S1009でエッジ処理部301は、エッジリストからエッジノード、エッジ更新リストからエッジ更新ノードをそれぞれ外し、エッジノードとエッジ更新ノードをメモリから解放する。
【００３５】
S1010でエッジ処理部301は、CntYをインデックス値として垂直エッジ管理テーブルを参照し、垂直エッジ管理テーブルに格納されている値がNULL以外の場合S1011へ進み、NULLの場合はエッジ更新処理を終了する。S1011でエッジ処理部301は、エッジリストからエッジノードを外しメモリ上からの解放、及びエッジ更新リストあるいは、垂直エッジ更新リストからエッジ更新ノードを外しメモリ上からの解放を行なう。
【符号の説明】
【００３６】
707エッジリスト
714エッジ更新リスト
718垂直エッジ管理テーブル
719垂直エッジ更新リスト
【図１】
2012159963.tif 000003
【図２】
2012159963.tif 000004
【図３】
2012159963.tif 000005
【図４】
2012159963.tif 000006
【図５Ａ】
2012159963.tif 000007
【図５Ｂ】
2012159963.tif 000008
【図６】
2012159963.tif 000009
【図７Ａ】
2012159963.tif 000010
【図７Ｂ】
2012159963.tif 000011
【図８】
2012159963.tif 000012
【図９】
2012159963.tif 000013
【図１０】
2012159963.tif 000014