(57)【要約】【課題】エッジリスト登録時にオーバーフローが発生した場合でもエッジリストに登録されただけの範囲のエッジ情報を使用して描画処理を行う。【解決手段】情報処理装置（１）はエッジリストを作成するエッジリスト生成部（１６３）を含む。このエッジリスト生成部には、分割描画のための最大エッジ数が設定される最大エッジ数レジスタと、エッジリスト作成のために処理されるエッジの個数と、最大エッジ数レジスタに設定されている最大エッジ数とをスキャンライン毎に比較し、その比較結果に基づいて、図形の分割描画における分割箇所をスキャンライン毎に決定する分割描画判定部とを設ける。これにより、1つのスキャンラインにおいて全てのエッジについてのリストを1度に揃える必要がなくなる。【選択図】図１
2013015952.tif 000002
【特許請求の範囲】
【請求項１】
描画対象とされる図形における頂点間を結ぶ直線とスキャンラインとの交点の座標に基づいてエッジリストを作成するエッジリスト生成部を含み、生成されたエッジリストに従って上記図形の分割描画を行う情報処理装置であって、
上記エッジリスト生成部は、上記分割描画のための最大エッジ数が設定される最大エッジ数レジスタと、
上記エッジリスト作成のために処理されるエッジの個数と、上記最大エッジ数レジスタに設定されている最大エッジ数とを上記スキャンライン毎に比較し、その比較結果に基づいて、上記図形の分割描画における分割箇所を上記スキャンライン毎に決定する分割描画判定部と、を含むことを特徴とする情報処理装置。
【請求項２】
上記エッジリスト生成部は、エッジリストオーバーフロー判定レジスタを含み、
上記分割描画判定部は、作成中のエッジリストに登録されているエッジ数が、最大エッジ数レジスタに設定されている最大エッジ数に達した状態で、更なるエッジ登録が必要な場合に、オーバーフロー状態と判定して、上記エッジリストオーバーフロー判定レジスタに、オーバーフロー状態を示すフラグをセットする請求項１記載の情報処理装置。
【請求項３】
上記オーバーフロー状態を示すフラグは、上記エッジリスト又は上記スキャンライン毎に１ビット用意される請求項２記載の情報処理装置。
【請求項４】
上記エッジリストに登録可能な所定のエッジ数単位で上記分割描画が実行される請求項３記載の情報処理装置。
【請求項５】
上記オーバーフロー状態を示すフラグが解除されるまで、上記エッジリストの作成と、作成されたエッジリストに従う分割描画が繰返される請求項４記載の情報処理装置。
【請求項６】
上記エッジリストに登録可能な所定のエッジ数単位で上記分割描画が実行される毎に、描画データを外部画像出力装置に出力するためのビデオディスプレイコントローラを含む請求項５記載の情報処理装置。
【請求項７】
上記エッジリスト生成部は、座標値の小さい順に上記エッジリストに登録するための並べ替えを行うエッジソーティング部を含む請求項６記載の情報処理装置。
【請求項８】
上記エッジリスト生成部は、上記エッジソーティング部から出力された座標が、処理再開の座標の初期値以下の場合に、上記エッジリストへの登録のためのデータ書込みをマスクするためのライトマスク部を含む請求項７記載の情報処理装置。
【請求項９】
上記情報処理装置は、ＣＰＵを含み、
上記ＣＰＵは、上記エッジリストオーバーフロー判定レジスタにセットされたフラグの状態に基づいてエッジリストオーバーフロー状態を判定し、その後のエッジリスト作成の際に、同一入力データの再読込みを指示する請求項８記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理技術、さらには、ベクタグラフィックスにおいて、内蔵メモリを利用して図形の描画を行うために、一度に処理するデータ量を限定した分割描画を行う図形塗潰し描画技術に関する。
【背景技術】
【０００２】
特許文献１には、ベクタデータで表現された文字や図形をフレームバッファ等の二次元空間へ描画する技術が記載されている。それによれば、描画の対象となる図形の輪郭を表すベクタデータとスキャンラインとの交点となる座標を認識し、認識される座標を示す座標データを記憶し、座標数を１スキャンライン毎に算出し、算出された座標数が、予め割り当てられた１スキャンラインの座標データ数を越えるか否かを判断し、越えると判断された数の座標データを記憶するようにしている。
【０００３】
特許文献２には、システムに負荷をかけることなく、座標データの数に応じて最適な量の記憶領域を確保し、また、処理時間を短縮するための技術が記載されている。それによれば、ベクタ数が閾値より多い場合には、描画対象図形の特性である、各スキャンラインのエッジデータ数とバウンディングボックスのｙ座標の最大値・最小値とが先読みされる。そして、描画対象図形の特性に応じて、異なるアルゴリズムの動的領域確保部の中から、必要最小限の新たなエッジリスト領域を動的に確保するために適したものが選択され、選択された動的領域確保部を用いて、エッジデータを描画座標格納部に格納するか、描画座標格納部に格納するかが切り替えられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】２０００−１７２８５８号公報
【特許文献２】２００１−１０９８９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１，２にも記載されているように、図形塗潰し処理にはオーダードエッジリスト方式を用いることができる。オーダードエッジリスト方式によれば、先ず図形データの副走査方向の最小値と最大値を求めて有効スキャンラインが初期設定される。次に図形データを参照して、図形の輪郭とスキャンラインの交点の座標を求めて順次エッジリストに登録される。そのときエッジリストがオーバーフローしたか否かが判断され、オーバーフローしなければ全ての交点を登録した後エッジリストを整列化して塗潰しが行われる。一方、オーバーフローした場合には図形が分割され、有効スキャンラインが初期設定の半分の範囲に再設定された後に、再度全ての交点の座標が求められ、再設定された有効スキャンラインの範囲内の交点の座標値のみがエッジリストに登録され、オーバーフローがなければ再設定された有効スキャンラインの範囲のみの分割図形が塗潰される。図形塗潰し処理に必要なメモリの記憶容量を超えるエッジ数を含んだ形状を描画するためには、描画領域を分割して処理を行う手法をとる。描画領域の分割に伴い描画サイズが再設定され、再設定後の描画領域に含まれるエッジがオーバーフローを起こさず、メモリに納まるまで描画領域の分割が繰り返される。
【０００６】
しかしながら、描画領域の再設定を行う際、エッジ数が極端に多い場合には、描画領域の再設定とエッジリスト登録を繰り返し行うのみで描画の開始までに大きな時間を費やす可能性がある。また、描画領域の分割を繰り返したとしてもエッジが1ラインに納まり切れない場合には、描画不可能な状態に陥るおそれもある。
【０００７】
本発明の目的は、分割描画において、エッジリスト登録時にオーバーフローが発生した場合でもエッジリストに登録されただけの範囲のエッジ情報を使用して描画処理を行うための技術を提供することにある。
【０００８】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【０００９】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１０】
すなわち、描画対象とされる図形における頂点間を結ぶ直線とスキャンラインとの交点の座標に基づいてエッジリストを作成するエッジリスト生成部を含んで情報処理装置を構成する。上記エッジリスト生成部は、上記分割描画のための最大エッジ数が設定される最大エッジ数レジスタと、上記エッジリスト作成のために処理されるエッジの個数と、上記最大エッジ数レジスタに設定されている最大エッジ数とを上記スキャンライン毎に比較し、その比較結果に基づいて、上記図形の分割描画における分割箇所を上記スキャンライン毎に決定する分割描画判定部とを含む。
【発明の効果】
【００１１】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１２】
すなわち、分割描画において、エッジリスト登録時にオーバーフローが発生した場合でもエッジリストに登録されただけの範囲のエッジ情報を使用して描画処理を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】本発明にかかる情報処理装置の一例とされるマイクロコンピュータの構成例ブロック図である。
【図２】図１に示されるマイクロコンピュータにおける主要部の構成例ブロック図である。
【図３】オーダードエッジリスト方式によるエッジリスト作成の説明図である。
【図４】オーダードエッジリスト方式により作成されたエッジリストの説明図である。
【図５】ディスプレイ設定サイズ及びエッジ数の設定と、必要なメモリサイズとの関係説明図である。
【図６】エッジリストの構成例説明図である。
【図７】エッジデータ登録の説明図である。
【図８】図１に示されるマイクロコンピュータにおける主要部の構成例ブロック図である。
【図９】エッジリスト生成及び描画についての全体的なフローチャートである。
【図１０】図９における主要部の詳細なフローチャートである。
【図１１】初回のエッジリスト作成における１個目のエッジリスト登録の説明図である。
【図１２】初回のエッジリスト作成における２個目のエッジリスト登録の説明図である。
【図１３】初回のエッジリスト作成における３個目のエッジリスト登録の説明図である。
【図１４】初回のエッジリスト作成における４個目のエッジリスト登録の説明図である。
【図１５】初回のエッジリスト作成における５個目のエッジリスト登録の説明図である。
【図１６】初回のエッジリスト作成における６個目のエッジリスト登録の説明図である。
【図１７】２回目のエッジリスト作成における１個目のエッジリスト登録の説明図である。
【図１８】２回目のエッジリスト作成における２個目のエッジリスト登録の説明図である。
【図１９】２回目のエッジリスト作成における３個目のエッジリスト登録の説明図である。
【図２０】２回目のエッジリスト作成における４個目のエッジリスト登録の説明図である。
【図２１】２回目のエッジリスト作成における５個目のエッジリスト登録の説明図である。
【図２２】２回目のエッジリスト作成における６個目のエッジリスト登録の説明図である。
【図２３】従来のオーダードエッジリスト方式による図形塗潰しについての説明図である。
【図２４】図１に示されるマイクロコンピュータでの図形塗潰しについての説明図である。
【図２５】図１に示されるマイクロコンピュータでの図形塗潰しについての説明図である。
【図２６】図１に示されるマイクロコンピュータでの図形塗潰しについての説明図である。
【発明を実施するための形態】
【００１４】
１．実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００１５】
〔１〕本発明の代表的な実施の形態に係る情報処理装置（１）は、描画対象とされる図形における頂点間を結ぶ直線とスキャンラインとの交点の座標に基づいてエッジリストを作成するエッジリスト生成部（１６３）を含み、生成されたエッジリストに従って上記図形の分割描画を行う。上記エッジリスト生成部は、上記分割描画のための最大エッジ数が設定される最大エッジ数レジスタ（１６４０）と、上記エッジリスト作成のために処理されるエッジの個数と、上記最大エッジ数レジスタに設定されている最大エッジ数とを上記スキャンライン毎に比較し、その比較結果に基づいて、上記図形の分割描画における分割箇所を上記スキャンライン毎に決定する分割描画判定部（１６３５）とを含む。
【００１６】
上記の構成によれば、分割描画判定部は、上記エッジリスト作成のために処理されるエッジの個数と、上記最大エッジ数レジスタに設定されている最大エッジ数とを上記スキャンライン毎に比較し、その比較結果に基づいて、上記図形の分割描画における分割箇所を上記スキャンライン毎に決定する。これにより、1つのスキャンラインにおいて全てのエッジについてのリストを1度に揃える必要がなくなるので、様々な形状を描画することが可能であり、しかも、比較的小容量の内蔵ＲＡＭ（２１）で図形塗潰しを実現することができる。
【００１７】
〔２〕上記〔１〕において、上記エッジリスト生成部（１６３）は、エッジリストオーバーフロー判定レジスタ（１６３９）を含んで構成することができる。このとき、上記分割描画判定部（１６３５）は、作成中のエッジリストに登録されているエッジ数が、最大エッジ数レジスタに設定されている最大エッジ数に達した状態で、更なるエッジ登録が必要な場合に、オーバーフロー状態と判定して、上記エッジリストオーバーフロー判定レジスタ（１６３９）に、オーバーフロー状態を示すフラグをセットするように構成することができる。
【００１８】
〔３〕上記〔２〕において、上記オーバーフロー状態を示すフラグは、上記エッジリスト又は上記スキャンライン毎に１ビット用意することができる。
【００１９】
〔４〕上記〔３〕において、上記エッジリストに登録可能な所定のエッジ数単位で上記分割描画を実行することができる。
【００２０】
〔５〕上記〔４〕において、上記オーバーフロー状態を示すフラグが解除されるまで、上記エッジリストの作成と、作成されたエッジリストに従う分割描画が繰返されるように構成することができる。
【００２１】
〔６〕上記〔５〕において、上記エッジリストに登録可能な所定のエッジ数単位で上記分割描画が実行される毎に、描画データを外部画像出力装置に出力するためのビデオディスプレイコントローラ（１７）を設けることができる。
【００２２】
〔７〕上記〔６〕において、上記エッジリスト生成部に、座標値の小さい順に上記エッジリストに登録するための並べ替えを行うエッジソーティング部（１６３３）を設けることができる。
【００２３】
〔８〕上記〔７〕において、上記エッジリスト生成部には、上記エッジソーティング部から出力された座標が、処理再開の座標の初期値以下の場合に、上記エッジリストへの登録のためのデータ書込みをマスクするためのライトマスク部（１６３４）を設けることができる。
【００２４】
〔９〕上記〔８〕において、上記情報処理装置は、ＣＰＵ（１１）を含んで構成することができる。この場合において、上記ＣＰＵは、上記エッジリストオーバーフロー判定レジスタにセットされたフラグの状態に基づいてエッジリストオーバーフロー状態を判定し、その後のエッジリスト作成の際に、同一入力データの再読込みを指示するように構成することができる。
【００２５】
２．実施の形態の詳細
実施の形態について更に詳述する。
【００２６】
《実施の形態１》
図１には、本発明にかかる情報処理装置の一例とされるマイクロコンピュータが示される。図１に示されるマイクロコンピュータ１は、特に制限されないが、速度計やタコメータ等の表示、及び燃費情報などのドライバインフォメーション等の表示を可能にする車載ディスプレイシステムに搭載される。マイクロコンピュータ１は、特に制限されないが、ＣＰＵ（中央処理装置）コア１１、キャッシュコントローラ１３、キャッシュ１４、歪み補正エンジン１５、ベクタグラフィックプロセッサ１６、ビデオディスプレイコントローラ１７、ＳＤ／ＭＭＣインタフェース１９、ＣＤ−ＲＯＭインタフェース２０、内蔵ＲＡＭ（ランダムアクセスメモリ）２１、バスステートコントローラ２２を含む。マイクロコンピュータ１は、公知の半導体集積回路製造技術により単結晶シリコン基板などの一つの半導体基板に形成することができる。
【００２７】
ＣＰＵコア１１は、予め設定されたプログラムを実行することによって、マイクロコンピュータ全体の動作制御を司る。ＣＰＵコア１１には、ＣＰＵバス１２を介してキャッシュコントローラ１３及びキャッシュメモリ１４が結合される。キャッシュコントローラ１４は、使用頻度の高いデータをキャッシュメモリ１４に蓄えておくことによりデータアクセスを高速化するために設けられる。歪み補正エンジン１５は、トライアングルメッシュと呼ぶレンダリング技術を用いて歪んだ画像を正常な画像に補正するエンジンで、魚眼レンズで撮影した画像を正常な画像へ変換するために設けられる。キャッシュコントローラ１３、キャッシュメモリ１４、歪み補正エンジン１５、ベクタグラフィックプロセッサ１６、ビデオディスプレイコントローラ１７、ＳＤ／ＭＭＣインタフェース１９、ＣＤ−ＲＯＭインタフェース２０、内蔵ＲＡＭ２１、バスステートコントローラ２２は、内部バス１８を介して互いに結合されている。ベクタグラフィックプロセッサ１６は、描画処理を行う。ビデオディスプレイコントローラ１７は、ベクタグラフィックプロセッサ１６での描画結果を外部画像出力装置２に表示させる。外部画像出力装置２は、ダッシュボードに設けられた液晶ディスプレイ２とされる。ＳＤ／ＭＭＣインタフェース１９は、ＳＤメモリカード又はマルチメディアカードとの間でデータのやり取りを可能にする。ＣＤ−ＲＯＭインタフェース２０は、外部データ入力装置（ＣＤ−ＲＯＭ）３との間でデータのやり取りを可能にする。内蔵ＲＡＭ２１は、ＣＰＵコア１１やベクタグラフィックプロセッサ１６によってランダムアクセス可能とされる。内蔵ＲＡＭ２１には、ベクタグラフィックプロセッサ１６で実行されるコマンドや、ベクタグラフィックプロセッサ１６での描画処理に供される図形データ、さらにはベクタグラフィックプロセッサ１６での描画されたデータなどが格納される。バスステートコントローラ２２は、内部バス１８におけるバスステートを制御する。
【００２８】
ベクタグラフィックプロセッサ１６は、バスインタフェース１６０、命令デコーダ１６１、頂点処理部１６２、エッジリスト生成部１６３、塗潰し判定部１６４、及びピクセル処理部１６５を含む。バスインタフェース１６０は、内部バス１８を利用したデータのやり取りを可能にする。命令デコーダ１６１は、内蔵ＲＡＭ２１からフェッチされた命令をデコードする。頂点処理部１６２は、内蔵ＲＡＭ２１内のベクタデータを線分単位に区切るための二つの頂点を抽出する。エッジリスト生成部１６３は、分割描画のためのエッジリストを生成する。このエッジリストは、内蔵ＲＡＭ２１に格納される。塗潰し判定部１６４は、内蔵ＲＡＭ２１内のエッジリストを使用して塗潰し領域を判定する。ピクセル処理部１６５は、塗潰し判定部１６４での塗潰し判定結果に基づいてピクセル値を決定する。ピクセル処理部１６５でのピクセル処理結果は、内蔵ＲＡＭ２１に格納される。
【００２９】
図２には、エッジリスト生成部１６３の構成例が示される。
【００３０】
エッジリスト生成部１６３は、エッジ生成部１６３０、エッジリード部１６３１、ヘッダ情報保持部１６３２、エッジソーティング部１６３３、ライトマスク部１６３４、分割描画判定部１６３５、ライトデータ生成部１６３６、エッジライト部１６３７、分割描画カウンタ１６３８、エッジリストオーバーフロー判定レジスタ１６３９、及び最大エッジ数レジスタ１６４０を含む。
【００３１】
エッジ生成部１６３０は、入力された頂点座標を順に結びながら、エッジを形成する直線とスキャンラインとの交点の座標を求める。エッジリード部１６３１は、作成済みのヘッダデータを内蔵ＲＡＭ２１からリードし（読み出し）、ヘッダ情報保持部１６３２から伝達されたエッジ個数分のエッジデータを取り込む。エッジ生成部１６３０は、ヘッダデータをヘッダ情報保持部１６３２へ出力し、エッジデータをエッジソーティング部１６３３へ出力する。ヘッダ情報保持部１６３２は、ヘッダ情報のエッジ個数を保持し、それをエッジリード部１６３１と分割描画判定部１６３５に伝達する。ヘッダ情報保持部１６３２は、後に詳述するように、ヘッダ情報に各々二つある内外カウンタ及び処理再開ｘ座標から分割回数の偶数又は奇数に応じた値を初期値として選択する。さらにヘッダ情報保持部１６３２は、ヘッダ情報の内外カウンタの初期値を保持し、それをライトデータ生成部１６３６へ伝える。そしてヘッダ情報保持部１６３２は、ヘッダ情報の処理再開ｘ座標の初期値を保持し、それをライトマスク部１６３４へ伝える。エッジソーティング部１６３３は、エッジデータをｘ座標に従って昇順に再整列する（並べ替える）。ライトマスク部１６３４は、ライトデータのマスク処理を行う。この処理において、エッジソーティング部１６３３から出力されたｘ座標は、それが処理再開ｘ座標の初期値よりも大きい場合に、分割描画判定部１６３２へ伝達される。分割描画判定部１６３５は、ライトマスク部１６３４から伝達されたエッジデータの個数をカウントし、そのカウント値と、最大エッジ数レジスタ１６４０に保持されている最大エッジ数とを比較することによってオーバーフローの判定を行う。最大エッジ数レジスタ１６４０に保持されている最大エッジ数：ｍａｘ＿ｎは、ユーザによって予め設定されている。つまり、分割描画判定部１６３５は、ユーザによって予め設定されている最大エッジ数：ｍａｘ＿ｎと、作成中のエッジリストに登録されているエッジ数（ｎ）をスキャンライン毎に比較して、（ｍａｘ＿ｎ＜ｎ＋１）が成立した場合（ｎ個のエッジが登録されている状態で更なるエッジ登録が必要な場合）に「エッジリストオーバーフロー」となって、ｎ番目以降のエッジデータをライトしないようにライトデータ生成部１６３６を制御する。これにより分割箇所をスキャンライン毎に決定することができる。尚、オーバーフローしたときはエッジデータ個数のカウントは行われない。また、マスクされたデータを、回数を分けて次回以降に分割描画するために、エッジリストがオーバーフローしたことを、エッジリストオーバーフロー判定レジスタ１６３９を介してＣＰＵ１１に通知する。オーバーフローを示すフラグは、エッジスリスト又はスキャンライン毎に１ビット用意すれば十分である。ライトデータ生成部１６３６は、ヘッダ情報保持部１６３２から伝達された内外カウンタの初期値に、入力されたエッジデータの向きを加算して内外カウンタの値を更新することでライトデータを生成する。ライトデータ生成部１６３６は、分割描画判定部１６３５でのオーバーフロー判定結果がオーバーフローではないとき、入力されたエッジデータのｘ座標を処理再開ｘ座標として保持する。ライトデータ生成部１６３６は、分割描画判定部１６３５でのオーバーフロー判定結果がオーバーフロー時に、入力されたｘ座標と処理再開ｘ座標が同一の場合には、エッジの向きを計算して保持するとともに、それをエッジライト部１６３７へ伝え、エッジデータをライトした後にヘッダデータをライトするようにエッジライト部１６３７に伝える。また、ライトデータ生成部１６３６は、分割描画判定部１６３５のオーバーフロー判定結果がオーバーフロー時に、入力されたｘ座標と処理再開ｘ座標が同一ではない場合は、ヘッダデータをライトするようにエッジライト部１６３７に伝える。エッジライト部１６３０は、ヘッダデータをライトする時は、分割描画判定部１６３５より「エッジ個数」、ライトデータ生成部より「内外カウンタ値」と「処理再開ｘ座標」を内蔵ＲＡＭ２１へライトする。エッジライト部１６３０は、エッジデータをライトする時は、ライトデータ生成部から入力されたエッジデータを内蔵ＲＡＭ２１にライトする（書き込む）。
【００３２】
エッジリストは、次のように作成することができる。
【００３３】
図３には、ベクトルデータの例が示され、図４には、図３のベクトルデータに対応するエッジリストが示される。図３においてｘ軸とｙ軸とは互いに直交する。ベクタグラフィックプロセッサ１６では、オーダードエッジリスト方式による塗潰し処理が行われる。つまり、描画処理の対象とされる図形の頂点を順に結びながら、エッジを形成する直線とｙ＝０〜８の各スキャンラインとの交点の座標が求められ、それに基づいてエッジリストが作成される。エッジリストは、図３における矢印３１〜３６の順に生成される。３個の頂点３７については、二度書き防止のため、エッジリスト生成時にエッジ無しと判断される。図３及び図４に示される例では、ｙ＝０〜８の各スキャンラインについて、それぞれ対応するエッジ数と、ｘ座標＋（エッジの向き）が示される。「エッジの向き」は、上向きが論理値‘１’で示され、下向きが論理値‘０’で示される。例えばｙ＝０のラインでは、エッジ数ｎ＝０であるが、ｙ＝１のラインでは、エッジ数ｎ＝２である。ｙ＝１のラインでの１個目のエッジは、４５０，１（ｘ座標が４５０でエッジが上向きであることを意味する）であり、２個目のエッジは、６７５，−１（ｘ座標が６７５でエッジが下向きであることを意味する）である。同様に、ｙ＝２のラインでのエッジ数ｎ＝２であり、１個目のエッジは、４００，１であり、２個目のエッジは、８７５，−１である。図３において、エッジで包囲された領域は、「塗潰し領域の内側」とされ、それ以外の領域は、「塗潰し領域の外側」とされる。ｙ方向（画面縦方向）は画面サイズ分のメモリ空間を消費する。1ラインサイズはユーザの判断で適宜変更可能なものとする。図５には、ディスプレイ設定サイズ及びエッジ数の設定と、必要なメモリサイズとの関係が示される。外部画像出力装置２がＱＶＧＡの場合とＶＧＡの場合とで必要なメモリサイズが異なる。１ライン当たり１２８エッジの場合、ＱＶＧＡでは６０Ｋバイト必要であるのに対して、ＶＧＡでは１２０Ｋバイト必要となる。１ライン当たり２５６エッジの場合、ＱＶＧＡでは１２０Ｋバイト必要であるのに対して、ＶＧＡでは２４０Ｋバイト必要となる。尚、処理の効率化を図るために、ダブルバッファ化する場合は更に２倍の記憶容量が必要となる。
【００３４】
図６には、エッジリストの構成が示される。
【００３５】
エッジリストはヘッダとエッジデータとを含む。ヘッダは、図６の（Ａ）に示されるように、エッジ数、塗潰し内外カウンタ値、処理再開ｘ座標を含む。エッジデータは、図６の（Ｂ）に示されるように、最大エッジ数分の（ｘ座標＋エッジの向き）が含まれる。「エッジの向き」は、上向きが論理値‘１’で示され、下向きが論理値‘０’で示される。「最大エッジ数」は、ユーザが設定可能な最大エッジ数レジスタ１６４０に設定することができる。
【００３６】
本例では、図形の分割描画が行われる。２回目以降の描画で「塗潰し内外カウンタ値」の情報が必要となる。前回の描画で塗潰し領域の内、外側のどちらで終了したかを知る必要がある。本例では、「０」以外の整数ならば「内側」、「０」は「外側」で終了したと判断するものとする。「処理再開ｘ座標」は処理済みのエッジのうち、最大のｘ座標とされる。このｘ座標を基準として、より大きいｘ座標を持ったエッジが、エッジリストに登録される。また、分割描画を行う際には、論理値‘０’と‘１’とを繰り返すトグル方式で描画回数を記憶する。この描画回数の記憶には、分割描画カウンタ１６３８を利用することができる。ヘッダには、塗潰し内外カウンタ値ｃｏｕｎｔ０，ｃｏｕｎｔ１の設定エリア、及び処理再開ｘ座標ｎｘｔ＿ｘ０，ｎｘｔ＿ｘ１の設定エリアが形成される。つまり、塗潰し内外カウンタ値ｃｏｕｎｔ０，ｃｏｕｎｔ１のうち、一方が初期値（生成エッジリストの前回情報）とされる（以降、これをｃｏｕｎｔ（ａ）とし、初期値としない方をｃｏｕｎｔ（ｂ）とする）。また、同様に処理再開ｘ座標ｎｘｔ＿ｘ０，ｎｘｔ＿ｘ１のうち、一方が初期値とされる（以降、これをｎｘｔ＿ｘ（ａ）とし、初期値としない方をｎｘｔ＿ｘ（ｂ）とする）。何れが初期値として選択されるかは、分割回数が奇数（１）か、偶数（０）かによって決定される。尚、初回（１回目）の通常描画においては、分割回数＝０となる。
【００３７】
次に、エッジリストへのエッジデータの登録方法について説明する。
【００３８】
エッジデータは、例えば図７の（Ａ）に示されるように、（ｘ座標＋エッジの向き）を単位として、最大エッジの数だけ登録される。
【００３９】
ここで、座標（ｘ、ｙ）（エッジの向き）＝（５，２）（１），（１０，２）（０），（１０，２）（１），（１５，２）（０），（１５，２）（１），（１５，２）（０），（１５，２）（１）とし、最大エッジ数＝５としたとき、エッジリストへの登録は以下のように行われる。
【００４０】
エッジリストへの登録処理は、データの左側から順番に行われる。この場合、ｘ＝５と、２個あるｘ＝１０に関しては、図７の（Ｂ）に示されるように、エッジリストに１データずつ登録が行われる。
【００４１】
２個あるｘ＝１０は、それぞれ別領域に登録することができる。しかし、図７の（Ｂ）の状態で、空きは残り２個であることから、４個あるｘ＝１５についての登録は上記の場合と異なる。すなわち、図７の（Ｃ）に示されるように、先ず、４個あるｘ＝１５のうち、最初に処理される「（１５，２）（０）」については、他のデータと同様にエッジリストに登録される。残り３個のｘ＝１５のデータは、エッジリストに登録するときに、エッジの向きではなく、エッジの向きの合計値をエッジリストにおける一つの登録エリアに登録される。本例では、エッジの向きの合計値は、１＋（−１）＋１＝１であるから、最後の登録エリアには、「１５，１」が登録される。
【００４２】
図８には、図１におけるピクセル処理部１６５の構成例が示される。
【００４３】
ピクセル処理部１６５は、エッジリード／ライト部１６５０、塗潰しｘ座標生成部１６５１、内外判定部１６５２、塗潰し部１６５３、及び描画結果ライト部１６５４を含む。
【００４４】
エッジリード／ライト部１６５０は、描画する図形に対して最小ｙ座標と最大ｙ座標を設定し、設定したｙ座標に対応する範囲内のヘッダデータを内蔵ＲＡＭ２１からリードして塗潰しｘ座標生成部１６５１に伝えてリードしたエッジ個数ｎを「０」にライトし、エッジデータを内蔵ＲＡＭ２１からリードして内外判定部１６５２に伝える。また、エッジリード／ライト部１６５０は、リードしたエッジ個数ｎを「０」にライトする前のヘッダデータのエッジ個数ｎを保持し、エッジデータを内蔵ＲＡＭ２１からｎ回リードする。エッジリード／ライト部１６５０は、設定された最大エッジ数ｍａｘ＿ｎを保持し、エッジリード／ライト部１６５０は、エッジ個数ｎに従ってリードされたエッジの数がｍａｘ＿ｎと等しい場合に、内外判定部１６５２に対して計算方法の変更を伝える。エッジリード／ライト部１６５０は、エッジ個数ｎが「０」の場合、塗潰しｘ座標生成部にヘッダデータを伝えない。エッジリード／ライト部１６５０は、ヘッダデータにある２個の処理再開ｘ座標のうち、分割回数の偶数又は奇数によって計算の初期値に使用する値を決めて、それを塗潰しｘ座標生成部へ伝える。そしてエッジリード／ライト部１６５０は、ヘッダデータにある２個の内外カウンタのうち、分割回数の偶数又は奇数によって計算の初期値に使用する値を決めて内外判定部１６５２へ伝える。
【００４５】
塗潰しｘ座標生成部１６５１は、設定された描画する図形に対して最大のｘ座標を保持する。エッジリード／ライト部１６５０からヘッダデータが入力された時、上記塗潰し開始ｘ座標から上記最大のｘ座標まで1づつインクリメントして、それを内外判定部１６５２へ伝える。また、塗潰しｘ座標生成部１６５１は、内外判定部１６５２からのインクリメント打ち切り要求に従い、インクリメントを停止する。
【００４６】
内外判定部１６５２は、塗潰しｘ座標生成部１６５１で決められた内外カウンタの初期値を使用してエッジデータの向きを計算し、処理を行うｘ座標が塗潰し領域内であるか、塗潰し領域外であるかの判定を行う。エッジリード／ライト部１６５０によって計算方法が変更された場合、エッジの向きの代わりにエッジの内外計算値を使用し、内外判定の値を更新する。内外判定部１６５２は、エッジリード／ライト部１６５０によって計算方法が変更された場合、塗潰し部へデータを伝えた後、塗潰しｘ座標生成部の処理を打ち切る。そして内外判定部１６５２は、エッジリード／ライト部１６５０から入力されたｘ座標と塗潰しｘ座標生成部から入力されたｘ座標を比較する。この比較の結果、ｘ座標生成部から入力されたｘ座標が小さい場合、内外判定の値とｘ座標を塗潰し部１６５３へ伝える。エッジリード／ライト部１６５０から入力されたｘ座標と塗潰しｘ座標生成部から入力されたｘ座標との比較の結果、ｘ座標生成部から入力されたｘ座標が大きい場合、又はそれらが互いに等しい場合、エッジリード／ライト部１６５０のからエッジデータを受け取り、内外判定を更新する。
【００４７】
塗潰し部１６５３は、内外判定部１６５２から入力されたｘ座標と内外判定の値を使用して塗潰しを行い、描画結果ライト部１６５４へ結果を伝える。
【００４８】
描画結果ライト部１６５４は、塗潰し部１６５３から入力された塗潰し結果を内蔵ＲＡＭ２１へライトする。
【００４９】
図９には、上記マイクロコンピュータ１によるエッジリスト生成及び描画処理の流れが示される。
【００５０】
先ず、ＣＰＵコア１１によって各種レジスタ等の初期設定が行われる（Ｓ１）。この初期設定においては、最大エッジ数レジスタ１６４０における最大エッジ数ｍａｘ＿ｎがユーザの指定値に設定される。エッジリストオーバーフロー判定レジスタ１６３９は、論理値‘０’（非オーバーフロー状態を意味する）に設定される。分割描画カウンタ１６３８が「０」に設定される。また、エッジリストがクリアされて初期状態にされる。
【００５１】
次に、エッジリストの作成が行われ（Ｓ２）、作成されたエッジリストに従って塗潰し（描画）処理が行われる（Ｓ３）。また、この塗潰し処理において、読み込んだヘッダ内のエッジ数を示す「ｎ」の値が「０」にクリアされる。
【００５２】
そして、ＣＰＵコア１１によってエッジリストオーバーフロー判定レジスタ１６３９が参照され、それに基づいてエッジリストがオーバーフローしたか否かの判別が行われる（Ｓ４）。上記ステップＳ４の判別において、エッジリストがオーバーフローした（Ｙｅｓ）と判断された場合には、２回目の描画用のエッジリストを作るために、同一データの再読込みが行われて再設定が行われた後に（Ｓ５）、上記ステップＳ２のエッジリスト作成に戻る。上記ステップＳ５の再設定では、エッジリストオーバーフロー判定レジスタ１６３９は、論理値‘０’（非オーバーフロー状態を意味する）に設定され、分割描画カウンタ１６３８に対して＋１のインクリメントが行われる。また、上記ステップＳ４の判別において、エッジリストがオーバーフローしていない（Ｎｏ）と判断された場合には処理が終了される。
【００５３】
図１０の（Ａ）には、図９におけるエッジリスト作成（Ｓ２）の処理の詳細な流れが示される。また、図１０の（Ｂ）には、同図（Ａ）におけるライトデータ生成処理（ＪＵＤＧＥ）の詳細な流れが示される。
【００５４】
エッジ生成部１６３０は、入力された２頂点を結ぶエッジとスキャンラインとの交点のｘ，ｙ座標を例えばブレゼンハムの直線補間方法を用いて求める（Ｓ２１）。
【００５５】
エッジリード部１６３１は、上記ステップＳ２１で求められたｘ，ｙ座標から内蔵ＲＡＭ２１のアドレス信号を生成し、内蔵ＲＡＭ２１内のエッジリストからヘッダデータをリードする（Ｓ２２）。
【００５６】
そして、ヘッダデータにあるエッジリスト内のエッジ登録数「ｎ」をアドレス生成回数として適宜の内部レジスタに設定し（図１０（Ａ）では“Ｒ”に相当）、エッジを書き戻す回数として適宜の内部レジスタを０に初期化し（図１０（Ａ）では“Ｎ”に相当）、塗潰し内外カウンタ値及び処理再開ｘ座標を初期化する（Ｓ２３）。つまり、ヘッダデータにある初期値として使用しない方のｃｏｕｎｔ（ｂ）、ｎｘｔ＿ｘ（ｂ）を、初期値として使用する方のｃｏｕｎｔ（ａ）、ｃｏｕｎｔ（ａ）の値に初期化する（図６参照）。尚、エッジリストのオーバーフロー判定のために、分割描画判定部１６３５においてもエッジ登録数「Ｎ」の値が参照される。
【００５７】
そして、Ｒ＝０が成立するか否かの判別が行われる（Ｓ２４）。ここで、既に登録済みのエッジが内蔵ＲＡＭ２１に存在する場合（Ｒ＞０）には、エッジリード部１６３１によって、内蔵ＲＡＭ２１内から対応するエッジのｘ座標がリードされる（Ｓ２５）。このエッジリードが行われる度に、リード回数Ｒは１引かれる（Ｓ２６）。
【００５８】
次に、エッジソーティング部１６３３によってエッジソーティング（並べ替え）が行われる（Ｓ２７）。つまり、登録済みのエッジがある場合（ｎ＞０）に、新たに追加するエッジを含めてx座標の小さいものから順番に再整列が行われる。その後、ライトデータ生成処理（ＪＵＤＧＥ）が行われる。また、上記ステップＳ２４の判別で、Ｒ＝０が成立しない場合には、ライトデータ生成処理（ＪＵＤＧＥ）が行われ、その後、ヘッダライト処理が行われる（Ｓ３７）。
【００５９】
次に、ライトデータ生成処理（ＪＵＤＧＥ）について、図１０の（Ｂ）を参照しなが説明する。
【００６０】
ステップＳ２７で得られる出力頂点のｘ座標を「ｓｘ」とする。このライトデータ生成処理においては、ステップＳ２７で得られる出力頂点の条件に従ってライトマスク処理が行われる（Ｓ２８，Ｓ２９，Ｓ３０，Ｓ３１，Ｓ３２，Ｓ３３，Ｓ３４）。例えばｓｘ≦ｎｘｔ＿ｘ（ａ）が成立するか否かの判別が行われる（Ｓ２８）。この判別において、ｓｘ≦ｎｘｔ＿ｘ（ａ）が成立しない場合には、分割描画判定部１６３５内において、最大エッジ数レジスタ１６４０に設定されている「最大エッジ数：ｍａｘ＿ｎ」と、エッジを書き戻した回数「Ｎ」に１を加えたものとが比較される（Ｓ３０）。この比較において、Ｎ＋１＞ｍａｘ＿ｎが成立しない場合には、ライトマスクが無効とされる（Ｓ３４）。このとき、Ｎは更新（＋１）されるが、オーバーフローとはされない。また、上記ステップＳ３０の判別において、Ｎ＋１＞ｍａｘ＿ｎが成立する場合には、ｓｘ＝ｎｘｔ＿ｘ（ｂ）が成立するか否かの判別が行われる（Ｓ３１）。この判別において、ｓｘ＝ｎｘｔ＿ｘ（ｂ）が成立しない場合には、分割描画が必要と判断され、エッジリストはオーバーフロー状態とされる（Ｓ３３）。このとき、ステップＳ２７のエッジソーティング後のエッジデータについて、(ｍａｘ＿ｎ＋１)番目以降のエッジがエッジリストに登録されないようにマスクされる。つまり、ライトマスク部１６３４の出力に基づいて、ライトデータ生成部１６３６でのライトデータ生成が制限される。ただし、リストに登録済みの最大のx座標（ｎｘｔ＿ｘ（ｂ））と等しいx座標の場合は、上記ステップＳ３１で「Ｙｅｓ」と判断されるため、マスクされない（Ｓ３２）。このとき、Ｎは更新されない。また、オーバーフローとはされないが、エッジの向きの計算方法が変更される。
【００６１】
尚、ｎｘｔ＿ｘ（ａ）の値以下のx座標を持ったエッジの場合には、上記ステップＳ２８の判別で、「Ｙｅｓ」と判断されるため、マスクされる（Ｓ２９）。このとき、Ｎは更新されない。また、オーバーフローとはされない。
【００６２】
上記ステップＳ３２やＳ３４でライトマスクが無効とされた場合には、ライトデータ生成部１６３６により、ヘッダ情報が更新される（Ｓ３５）。つまり、エッジ登録数を示す「ｎ」、描画再開時に必要となる内外カウンタ「ｃｏｕｎｔ」、処理再開x座標「ｎｘｔ＿ｘ」が更新される。それらの生成に必要なデータは、ライトマスク部１６３４から出力されるエッジの個数、向き、座標が使用される。エッジ登録数を示す「ｎ」は、出力エッジの数をカウントすることで得られる「Ｎ」とする。ただしｍａｘ＿ｎ個登録時に、リストに登録済みの最大のx座標（ｎｘｔ＿ｘ (ａ））と同じx座標が出力された場合はカウントしない。「ｃｏｕｎｔ」は、各々のエッジの向きを表現した数値を加算することで得られる。処理再開「ｎｘｔ＿ｘ」は、随時出力されるエッジのｘ座標に置き換えられる。  
【００６３】
次に、エッジライト部１６３７により、エッジライトが行われる（Ｓ３６）。そして、エッジリストからのエッジリードを所定のリード回数（ｎ）だけ行ったか否かの判別が行われる（Ｓ２４）。エッジリードがｎ回行われていない（Ｎｏ）と判断された場合には、前述の処理を繰り返すためにＳ２５のエッジリードで次のエッジリードが行われる。ｍａｘ＿ｎ個目のエッジデータは分割描画判定部１６３５に保持され、(ｍａｘ＿ｎ＋１)個目のエッジの座標がn個目のエッジの座標と同一の場合、エッジの向きを計算してライトされる。上記ステップＳ２４の判別において、エッジリードがｎ回行われた（Ｙｅｓ）と判断された場合には、ｎ＋１個目のエッジについて処理を行うために、Ｓ２８からＳ３６の該当する処理を行う。
そして、上記ステップＳ３５のヘッダ情報がエッジリストに登録される（Ｓ３７）。
【００６４】
次に、以下の６個の座標（ｘ、ｙ）がエッジリスト生成部１６３に入力され、最大エッジ数ｍａｘ＿ｎ＝３の場合のエッジリスト作成について詳述する（例えばｙ座標が“２”の場合のエッジリストを示す）。
【００６５】
（ｘ，ｙ）＝（５，２），（１５，２），（１０，２），（１５，２），（２０，２），（１０，２）
エッジの向き＝上（１），上（１），下（０），上（１），下（０），上（１）
先ず、図１１〜１６に基づいてエッジリストへの初回登録について説明する。
【００６６】
図１１には、初回のエッジリスト作成における１個目のエッジリスト登録の様子が示される。
【００６７】
初回のエッジリスト作成における１個目のｘ座標は「５」であり、エッジの向きは上（１）である。
【００６８】
初回のエッジリスト作成における１個目のエッジリスト登録において、ステップＳ２２のヘッダリードは、ｎ＝０、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝０、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝０となる。
【００６９】
初回のエッジリスト作成における１個目のエッジリスト登録の場合、ステップＳ２３におけるリード回数（登録数）Ｒは「０」とされ、エッジライト数Ｎは「０」とされ、内外カウンタｃｏｕｎｔ１＝ｃｏｕｎｔ０に初期化され、処理再開ｘ座標ｎｘｔ＿ｘ１＝ｎｘｔ＿０に初期化される。
【００７０】
初回のエッジリスト作成における１個目のエッジリスト登録において、ステップＳ２４で、「Ｒ＝０」が成立し、エッジリードを行わず、ステップＳ２８に移る。ここで、ソート後のｘ座標ｓｘ＝５であるから、ステップＳ２８の判別では「ｓｘ（＝５）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【００７１】
ステップＳ３０の判別では「Ｎ＋１（＝１）＞ｍａｘ＿ｎ（＝３）」が成立せず、ステップＳ３４に移る。
【００７２】
ステップＳ３４の処理ではライトマスクは無効となり、Ｎ＝Ｎ＋１＝１とし、オーバーフローとしない。
【００７３】
初回のエッジリスト作成における１個目のエッジリスト登録の場合、ステップＳ３５のヘッダ情報の更新では、ｎ＝Ｎ、ｃｏｕｎｔ１＝ｃｏｕｎｔ１＋１、ｎｘｔ＿ｘ１＝ｘ＝５とされる。
【００７４】
これにより、ステップＳ３６でのエッジライトによって、ｘ座標（＋エッジの向き）は、「５，（１）」とされ、１個目のエッジ登録がなされる。また、ステップＳ３８のヘッダライトによって、ｎ＝１、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝５とされる。
【００７５】
図１２には、初回のエッジリスト作成における２個目のエッジリスト登録の様子が示される。
【００７６】
初回のエッジリスト作成における２個目のｘ座標は「１５」であり、エッジの向きは上（１）である。
【００７７】
初回のエッジリスト作成における２個目のエッジリスト登録において、ステップＳ２２のヘッダリードは、初回のエッジリスト作成における１個目のヘッダライト結果がそのままリードされるため、ｎ＝１、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝５となる。
【００７８】
初回のエッジリスト作成における２個目のエッジリスト登録の場合、ステップＳ２３におけるリード回数Ｒは「１」とされ、エッジライト数Ｎは「０」とされ、内外カウンタｃｏｕｎｔ１＝ｃｏｕｎｔ０に初期化され、処理再開ｘ座標ｎｘｔ＿ｘ１＝ｎｘｔ＿０に初期化される。
【００７９】
初回のエッジリスト作成における２個目のエッジリスト登録において、ステップＳ２４で、「Ｒ＝０」が成立しないため、ステップＳ２５のエッジリードでは、初回１個目のエッジライト結果がそのままリードされ、１個のｘ座標（＋エッジの向き）は、「５，（１）」となる。
【００８０】
ステップＳ２６の処理では、リード回数Ｒ＝Ｒ−１＝０とする。
【００８１】
ステップＳ２７の処理では、エッジソーティングが行われ、エッジの値の小さい「５，（１）」が出力される。
【００８２】
ステップＳ２８判別では「ｓｘ（＝５）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【００８３】
ステップＳ３０の判別では「Ｎ＋１（＝１）＞ｍａｘ＿ｎ（＝３）」が成立せず、ステップＳ３４に移る。
【００８４】
ステップＳ３４の判別ではライトマスクは無効となり、Ｎ＝Ｎ＋１＝１とし、オーバーフローとしない。
【００８５】
ステップＳ３５のヘッダ情報の更新では、ｎ＝Ｎ、ｃｏｕｎｔ１＝ｃｏｕｎｔ１＋１、ｎｘｔ＿ｘ１＝ｘ＝５とされる。
【００８６】
これにより、ステップＳ３６でのエッジライトによって、ｘ座標（＋エッジの向き）は、「５，（１）」とされ、１個目のエッジ登録がなされる。
【００８７】
次に、ステップＳ２４の処理に戻り、「Ｒ＝０」が成立するためエッジリードを行わず、ステップＳ２８に移る。
【００８８】
ステップＳ２８の判別では「ｓｘ（＝１５）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【００８９】
ステップＳ３０の判別では「Ｎ＋１（＝２）＞ｍａｘ＿ｎ（＝３）」が成立せず、ステップＳ３４に移る。
【００９０】
ステップＳ３４の判別ではライトマスクは無効となり、Ｎ＝Ｎ＋１＝２とし、オーバーフローとしない。
【００９１】
初回のエッジリスト作成における２個目のエッジリスト登録の場合、ステップＳ３５のヘッダ情報の更新では、ｎ＝Ｎ、ｃｏｕｎｔ１＝ｃｏｕｎｔ１＋１＋１、ｎｘｔ＿ｘ１＝ｘ＝１５とされる。
【００９２】
これにより、ステップＳ３６でのエッジライトによって、ｘ座標（＋エッジの向き）は、「５，（１）」「１５，（１）」とされ、１個目のエッジ登録に加えて２個目のエッジ登録がなされる。また、ステップＳ３７のヘッダライトによって、ｎ＝２、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝２、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝１５とされる。
【００９３】
図１３には、初回のエッジリスト作成における３個目のエッジリスト登録の様子が示される。
【００９４】
初回のエッジリスト作成における３個目のｘ座標は「１０」であり、エッジの向きは下（０）である。
【００９５】
初回のエッジリスト作成における３個目のエッジリスト登録において、２個目のエッジリスト登録と同様にステップＳ２１からステップＳ３６の処理を行うことにより、ｘ座標（＋エッジの向き）「５，（１）」「１０，（０）」「１５，（１）」のエッジリストが生成され、ヘッダはｎ＝０＋１＋１＋１＝３、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝ｃｏｕｎｔ１＋１＋（−１）＋１＝１、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝１５となる。
【００９６】
図１４には、初回のエッジリスト作成における４個目のエッジリスト登録の様子が示される。
【００９７】
初回のエッジリスト作成における４個目のｘ座標は「１５」であり、エッジの向きは上（１）である。
【００９８】
初回のエッジリスト作成における４個目のエッジリスト登録において、３個目のエッジリスト登録と同様にステップＳ２１からステップＳ３６の処理を行うことにより、ｘ座標（＋エッジの向き）「５，（１）」「１０，（０）」「１５，（１）」のエッジリストが生成された後、ステップＳ２８の処理に移る。
【００９９】
ステップＳ２８の判別では「ｓｘ（＝１５）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【０１００】
ステップＳ３０の判別では「Ｎ＋１（＝４）＞ｍａｘ＿ｎ（＝３）」が成立し、ステップＳ３１に移る。
【０１０１】
ステップＳ３１の判別では「ｓｘ（＝１５）＝ｎｘｔ＿ｘ（ｂ）（＝１５）」が成立し、ステップＳ３２に移る。
【０１０２】
ステップＳ３２処理ではライトマスクは無効となり、Ｎ（＝３）は更新せず、オーバーフローともしない。
【０１０３】
ステップＳ３５のヘッダ情報の更新では、ｎ＝Ｎ、ｃｏｕｎｔ１＝ｃｏｕｎｔ１＋１＋（−１）＋１＋１、ｎｘｔ＿ｘ１＝ｘ＝１５とされる。
【０１０４】
ステップＳ３６のエッジライトでは、ｘ座標（＋エッジの向き）は、「５，（１）」「１０，（０）」「１５，（２）」とされる。ここで、「１５，（２）」がライトされるのは、２個あるｘ＝１５についての扱いでエッジの向きの合計値が「１＋１＝２」となることに起因する（Ｓ３２，図７（Ｃ）参照）。また、ステップＳ３８のヘッダライトによって、ｎ＝３、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝２、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝１５とされる。
【０１０５】
図１５には、初回のエッジリスト作成における５個目のエッジリスト登録の様子が示される。
【０１０６】
初回のエッジリスト作成における５個目のｘ座標は「２０」であり、エッジの向きは下（０）である。
【０１０７】
初回のエッジリスト作成における５個目のエッジリスト登録において、４個目のエッジリスト登録と同様にステップＳ２１からステップＳ３６の処理を行うことにより、ｘ座標（＋エッジの向き）「５，（１）」「１０，（０）」「１５，（２）」のエッジリストが生成された後、ステップＳ２８の処理に移る。
【０１０８】
ステップＳ２８では「ｓｘ（＝２０）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【０１０９】
ステップＳ３０では「Ｎ＋１（＝４）＞ｍａｘ＿ｎ（＝３）」が成立し、ステップＳ３１に移る。
【０１１０】
ステップＳ３１では「ｓｘ（＝２０）＝ｎｘｔ＿ｘ（ｂ）（＝１５）」が成立せず、ステップＳ３３に移る。
【０１１１】
ステップＳ３３ではライトマスクを有効とし、Ｎは更新せず、新規エッジを加えることができずに分割描画判定部１６３５において、分割描画が必要と判断され、「エッジリストオーバーフロー」とされる。このため生成されるエッジリストは４個目のエッジリスト登録時と同様に、ｘ座標（＋エッジの向き）「５，（１）」「１０，（０）」「１５，（２）」である。また、エッジリストオーバーフロー判定レジスタ１６３９が‘１’（オーバーフロー状態）に設定される。
【０１１２】
ステップ３７のヘッダライトも４個目のエッジリスト登録時と同様で、ｎ＝３、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝２、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝１５とされる。
【０１１３】
図１６には、初回のエッジリスト作成における６個目のエッジリスト登録の様子が示される。
【０１１４】
初回のエッジリスト作成における６個目のｘ座標は「１０」であり、エッジの向きは上（１）である。
【０１１５】
初回のエッジリスト作成における６個目のエッジリスト登録において、ステップＳ２１からステップＳ３６の処理を行うことにより、ｘ座標（＋エッジの向き）「５，（１）」「１０，（０）」エッジリストが生成された後、ステップＳ２４の判別に移る。この時、エッジ「１０（１）」と「１５（２）」は未処理であり、Ｒ＝１である。
【０１１６】
ステップＳ２４の判別では条件不成立のためステップＳ２５に移り、ステップＳ２５〜Ｓ２７の処理を行った後、ステップＳ２８に移る。
【０１１７】
ステップＳ２８の判別では「ｓｘ（＝１０）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【０１１８】
ステップＳ３０の判別では「Ｎ＋１（＝３）＞ｍａｘ＿ｎ（＝３）」が成立せず、ステップＳ３４に移る。
【０１１９】
ステップＳ３４の処理ではライトマスクは無効となり、Ｎ＝Ｎ＋１＝２とし、オーバーフローとしない。
【０１２０】
処理を進め再びステップＳ２４に戻った時、Ｒ（＝０）＝０が成立するため、ステップＳ２８に移る。
【０１２１】
ステップＳ２８の判別では「ｓｘ（＝１５）≦ｎｘｔ＿ｘ０（＝０）」が成立せず、ステップＳ３０に移る。
【０１２２】
ステップＳ３０の判別では「Ｎ＋１（＝４）＞ｍａｘ＿ｎ（＝３）」が成立し、ステップＳ３１に移る。
【０１２３】
ステップＳ３１の判別では「ｓｘ（＝１５）＝ｎｘｔ＿ｘ（ｂ）（＝１０）」が成立せず、ステップＳ３３に移る。
【０１２４】
ステップＳ３３の処理ではライトマスクを有効とし、Ｎは更新せず、ｘ座標（＋エッジの向き）「５，（１）」「１０，（０）」「１０，（１）」である。  ステップ３７のヘッダライトでは、ｎ＝３、ｃｏｕｎｔ０＝０、ｃｏｕｎｔ１＝ｃｏｕｎｔ１＋１+（−１）+１=１、ｎｘｔ＿ｘ０＝０、ｎｘｔ＿ｘ１＝１０とされる。そしてこのようにして得られたエッジリストに従って、１度目の描画が行われる（Ｓ３）。この描画では、ｃｏｕｎｔ０のため、ｎｘｔ＿ｘ０＝０から１個目のエッジまでは塗潰しが行われない。１個目のエッジのｘ座標＝５は上向きのエッジ（１）で、ｃｏｕｎｔ０＋１＝１であるため、塗潰しが開始される。２個目のエッジのｘ座標＝１０は下向きのエッジ（０）で、ｃｏｕｎｔ０＋１＋（−１）＝０であるため、塗潰しが停止される。３個目のエッジのｘ座標＝１０は上向き（１）のエッジで、ｃｏｕｎｔ０＋１＝１であるため、塗潰しが開始される。
【０１２５】
ＣＰＵコア１１によってエッジリストオーバーフロー判定レジスタ１６３９が参照され、それに基づいてエッジリストがオーバーフローしたか否かの判別が行われる。この判別でエッジリストがオーバーフローした（Ｙｅｓ）と判断された場合には、同一データの再読込みが行われて再設定が行われた後に（Ｓ５）、上記ステップＳ２のエッジリスト作成に戻る。すなわち、初回のエッジリスト作成におけるエッジリスト作成の場合と同様に、以下の６個の座標（ｘ、ｙ）がエッジリスト生成部１６３に入力され、最大エッジ数ｍａｘ＿ｎ＝３の場合のエッジリスト作成が再び行われる。尚、ステップＳ５の再設定では、エッジリストオーバーフロー判定レジスタ１６３９は、論理値‘０’（非オーバーフロー状態を意味する）に設定され、分割描画カウンタ１６３８に対して＋１のインクリメントが行われる。
【０１２６】
（ｘ，ｙ）＝（５，２），（１５，２），（１０，２），（１５，２），（２０，２），（１０，２）
エッジの向き＝上（１），上（１），下（０），上（１），下（０），上（１）
ただし、２回目以降のエッジリスト作成において初期設定（Ｓ１）は省略される。
【０１２７】
図１７には、２回目のエッジリスト作成における１個目のエッジリスト登録の様子が示される。
【０１２８】
２回目のエッジリスト作成における１個目のｘ座標は「５」であり、エッジの向きは上（１）である。
【０１２９】
２回目のエッジリスト作成における１個目のエッジリスト登録の場合、ステップＳ２３におけるリード回数（登録数）Ｒは「０」とされ、エッジライト数Ｎは「０」とされ、分割カウンタが論理値‘１’とされることにより、内外カウンタｃｏｕｎｔ０＝ｃｏｕｎｔ１に初期化され、処理再開ｘ座標ｎｘｔ＿ｘ０＝ｎｘｔ＿ｘ１に初期化される。
【０１３０】
２回目のエッジリスト作成における１個目のエッジリスト登録において、ステップＳ２４で、「Ｒ＝０」が成立し、エッジリードを行わず、ステップＳ２８に移る。
【０１３１】
ステップＳ２８の判別では「ｓｘ（＝５）≦ｎｘｔ＿ｘ１（＝１０）」が成立し、ステップＳ２９に移る。
【０１３２】
ステップＳ２９の判別ではライトマスクを有効として、Ｎ（＝０）は更新せず、オーバーフローとはしない。
【０１３３】
図１８には、２回目のエッジリスト作成における２個目のエッジリスト登録の様子が示される。
【０１３４】
２回目のエッジリスト作成における２個目のｘ座標は「１５」であり、エッジの向きは上（１）である。
【０１３５】
２回目のエッジリスト作成における２個目のエッジリスト登録において、ステップＳ２４で、「Ｒ＝０」が成立し、エッジリードを行わず、ステップＳ２８に移る。
【０１３６】
ステップＳ２８の判別では「ｓｘ（＝１５）≦ｎｘｔ＿ｘ１（＝１０）」が成立せず、ステップＳ３０に移る。
【０１３７】
ステップＳ３０の判別では「Ｎ＋１（＝１）＞ｍａｘ＿ｎ（＝３）」が成立せず、ステップＳ３４に移る。
【０１３８】
ステップＳ３４の処理ではライトマスクは無効となり、Ｎ＝Ｎ＋１＝１とし、オーバーフローとしない。
【０１３９】
２回目のエッジリスト作成における２個目のエッジリスト登録の場合、ステップＳ３５のヘッダ情報の更新では、ｎ＝Ｎ、ｃｏｕｎｔ０＝ｃｏｕｎｔ０＋１、ｎｘｔ＿ｘ０＝ｘ＝１５とされる。
【０１４０】
これにより、ステップＳ３６でのエッジライトによって、ｘ座標（＋エッジの向き）は、「１５，（１）」とされ、１個目のエッジ登録がなされる。また、ステップＳ３７のヘッダライトによって、ｎ＝１、ｃｏｕｎｔ０＝２、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝１５、ｎｘｔ＿ｘ１＝１０とされる。
【０１４１】
図１９には、２回目のエッジリスト作成における３個目のエッジリスト登録の様子が示される。
【０１４２】
これまでと同様の処理を繰り返すことにより、２回目のエッジリスト作成における３個目のエッジリスト登録では、ｘ座標（＋エッジの向き）は、「１５，（１）」、ヘッダ情報、ｎ＝１、ｃｏｕｎｔ０＝２、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝１５、ｎｘｔ＿ｘ１＝１０のエッジリストが生成される。
【０１４３】
図２０には、２回目のエッジリスト作成における４個目のエッジリスト登録の様子が示される。
【０１４４】
これまでと同様の処理を繰り返すことにより、２回目のエッジリスト作成における４個目のエッジリスト登録では、ｘ座標（＋エッジの向き）は、「１５，（１）」「１５，（１）」、ヘッダ情報、ｎ＝２、ｃｏｕｎｔ０＝３、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝１５、ｎｘｔ＿ｘ１＝１０のエッジリストが生成される。
【０１４５】
図２１には、２回目のエッジリスト作成における５個目のエッジリスト登録の様子が示される。
【０１４６】
これまでと同様の処理を繰り返すことにより、２回目のエッジリスト作成における５個目のエッジリスト登録では、ｘ座標（＋エッジの向き）は、「１５，（１）」「１５，（１）」「２０，（０）」、ヘッダ情報、ｎ＝３、ｃｏｕｎｔ０＝２、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝２０、ｎｘｔ＿ｘ１＝１０のエッジリストが生成される。
【０１４７】
図２２には、２回目のエッジリスト作成における３個目のエッジリスト登録の様子が示される。
【０１４８】
これまでと同様の処理を繰り返すことにより、２回目のエッジリスト作成における３個目のエッジリスト登録では、ｘ座標（＋エッジの向き）は、「１５，（１）」「１５，（１）」「２０，（０）」、ヘッダ情報、ｎ＝３、ｃｏｕｎｔ０＝２、ｃｏｕｎｔ１＝１、ｎｘｔ＿ｘ０＝２０、ｎｘｔ＿ｘ１＝１０のエッジリストが生成される。このエッジリストに従って２度目の描画が行われる。
【０１４９】
このような分割描画処理によれば、例えば最大エッジ数＝２とした場合の１回目の描画処理で、図２５の（Ａ）に示されるような図形２５０が形成された場合、２回目の描画処理では、１回目で処理されたｙ座標上に対して処理が追加されて図形２５１〜２５３が形成されることにより、描画対象とされる図形の描画処理が完了する。尚、図２５に示される例では、描画対象とされる図形の描画が２回の分割描画で完了しているが、図２６の（Ａ）〜（Ｆ）に示されるように、描画対象とされる図形の描画が６回の分割描画で完了する場合もあり得る。
【０１５０】
ここで、従来のオーダードエッジリスト方式による図形塗潰しにおいては、例えば図２３に示されるように、読み込んだエッジリストを使用して、最左のｘ座標から描画が開始される。つまり、描画対象とされる図形を囲む外接四角形２３１が設定され、最小座標点２３２、最大座標点２３３が定義され、最小座標点２３２から塗潰しが開始される。このような図形塗潰しにおいては、図形の輪郭とスキャンラインの交点の座標データ量がエッジリストを格納するメモリ容量を越えた場合に図形の塗潰しができないおそれがある。またエッジリストサイズが図形形状に依存するため、多様な図形描画に対応するためには大きなメモリが必要となるが、そのような大容量メモリを内蔵するとコストが非常に高くなる。
【０１５１】
これに対して、この実施の形態による図形塗潰しにおいては、初回（１回目）の描画処理を除いて、エッジ数を基準にエッジリスト生成が行われるため、塗潰し開始ｘ座標が全てのｙ座標で同一とは限らない。例えば図２４に示されるように、最大エッジ数ｍａｘ＿ｎ＝３、２回目の描画（分割描画カウンタ１６３８＝１）の場合、座標点２４１、２４２、２４３、２４４のｘ座標から描画が開始（再開）される。このようにエッジ数を基準にしてエッジリストを複数回に分けて作成して利用することにより、1つのスキャンライン（ｙ座標）について全てのエッジについてのリストを1度に揃える必要はなくなるので、様々な形状を描画することが可能であり、しかも、小容量の内蔵ＲＡＭ２１で図形塗潰しを実現することができる。
【０１５２】
また、この実施の形態ではｙ座標が“２”の場合を例に説明したが、もちろん全てのｙ座標（スキャンライン）に対応したエッジリストが同様に作成され、処理された後、描画される。それにより、複数回の描画処理を行う場合には、ｙ座標毎に異なるｘ座標から描画が再開され、例えば図２５や図２６に示されるように、複雑な形状のパズルのピースを組合せるような描画（パズル描画、部分描画、分割描画）を実現することが可能となる。これにより、複雑な形状の描画を小容量の内蔵ＲＡＭで実現することができるようになり、コスト削減にも寄与できる。
【０１５３】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。
【符号の説明】
【０１５４】
１  マイクロコンピュータ
２  外部画像出力装置
３  外部データ入力装置
１１  ＣＰＵコア
１２  ＣＰＵバス
１３  キャッシュコントローラ
１４  キャッシュメモリ
１５  歪み補正エンジン
１６  ベクタグラフィックプロセッサ
１７  ビデオディスプレイコントローラ
１８  内部バス
１９  ＳＤ／ＭＭＣインタフェース
２０  ＣＤ−ＲＯＭインタフェース
２１  内蔵ＲＡＭ
２２  バスステートコントローラ
１６０  バスインタフェース
１６１  命令デコーダ
１６２  頂点処理部
１６３  エッジリスト生成部
１６４  塗潰し判定部
１６５  ピクセル処理部
１６３０  エッジ生成部
１６３１  エッジリード部
１６３２  ヘッダ情報保持部
１６３３  エッジソーティング部
１６３４  ライトマスク部
１６３５  分割描画判定部
１６３６  ライトデータ生成部
１６３７  エッジライト部
１６５０  エッジリード／ライト部
１６５１  塗潰しｘ座標生成部
１６５２  内外判定部
１６５３  塗潰し部
１６５４  描画結果ライト部
【図１】
2013015952.tif 000003
【図２】
2013015952.tif 000004
【図３】
2013015952.tif 000005
【図４】
2013015952.tif 000006
【図５】
2013015952.tif 000007
【図６】
2013015952.tif 000008
【図７】
2013015952.tif 000009
【図８】
2013015952.tif 000010
【図９】
2013015952.tif 000011
【図１０】
2013015952.tif 000012
【図１１】
2013015952.tif 000013
【図１２】
2013015952.tif 000014
【図１３】
2013015952.tif 000015
【図１４】
2013015952.tif 000016
【図１５】
2013015952.tif 000017
【図１６】
2013015952.tif 000018
【図１７】
2013015952.tif 000019
【図１８】
2013015952.tif 000020
【図１９】
2013015952.tif 000021
【図２０】
2013015952.tif 000022
【図２１】
2013015952.tif 000023
【図２２】
2013015952.tif 000024
【図２３】
2013015952.tif 000025
【図２４】
2013015952.tif 000026
【図２５】
2013015952.tif 000027
【図２６】
2013015952.tif 000028