(57)【要約】【課題】目的とする多角形の形状に基づき高速な描画を行う描画装置を得る。【解決手段】多角形形状判定部２２が描画対象の多角形を特定する頂点データに基づき変曲点を検出し、多角形はＹ軸座標が単調増加あるいは単調減少するｙ単調多角形であるか否か判定し、多角形がｙ単調多角形である場合に、三角形分割部２３が頂点データに基づき多角形内を複数の三角形に分割して三角形分割データを生成し、多角形がｙ単調多角形でない場合に、ステンシル処理部２４が頂点の描画順序に基づき多角形をステンシル方式で描画してステンシルデータを生成し、生成された三角形分割データおよびステンシルデータに基づき、マスク作成部２５が描画箇所を特定箇所に制限するマスクパターンを作成する。【選択図】図１
2010072808.tif 000002
【特許請求の範囲】
【請求項１】
描画対象の多角形を特定する頂点データに基づき変曲点を検出し、前記多角形はＹ軸座標が単調増加あるいは単調減少するｙ単調多角形であるか否か判定する多角形形状判定部と、
前記多角形がｙ単調多角形である場合に、前記頂点データに基づき前記多角形内を複数の三角形に分割して三角形分割データを生成する三角形分割部と、
前記多角形がｙ単調多角形でない場合に、頂点の描画順序に基づき前記多角形をステンシル方式で描画してステンシルデータを生成するステンシル処理部と、
前記三角形分割データおよび前記ステンシルデータに基づき、描画箇所を特定箇所に制限するマスクパターンを作成するマスク作成部と、
前記多角形に外接する矩形であるバウンディングボックスを用いて、前記マスクパターンの上から前記多角形の塗りつぶしを行い描画する描画部と、
前記描画された多角形を外部装置に出力する表示処理部とを備えることを特徴とする描画装置。
【請求項２】
ステンシル処理部は、頂点データに基づき描画対象の多角形の重心を算出する重心算出部を備え、前記算出した重心を描画順序の開始点に設定してステンシル方式の描画を行うことを特徴とする請求項１記載の描画装置。
【請求項３】
ステンシル処理部は、バウンディングボックスの中点を算出する中点算出部を備え、前記算出した中点を描画順序の開始点に設定してステンシル方式の描画を行うことを特徴とする請求項１記載の描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、表示すべき図形を表す描画データを作成する描画装置に関するものである。
【背景技術】
【０００２】
従来、予め検出したメモリリソースの状態に応じて、ステンシル方式が利用可能か否か判定し、利用可能な場合にはステンシルバッファを利用するための描画データ生成および処理を行い、利用不可能な場合には線分分割方式、あるいは三角形分割方式のうち処理速度の速い方法を選択して利用する描画装置が提案されている（例えば、特許文献１参照）。また、多角形データが凹部多角形か否か判定し、凹部多角形であれば予め凸部多角形に分割し、さらに凸多角形から三角形分割を行い描画する方法も提案されている（例えば、特許文献２参照）。
【０００３】
【特許文献１】特開２００７−２６４９８９号公報
【特許文献２】特開２００２−１６３６６５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の描画装置は以上のように構成されているので、あらかじめ検出したメモリリソースの状態からステンシル方式を用いるかどうかの分岐判断を行うことによりメモリリソースの問題を解決しており、目的とする多角形の状態に最適な描画方法を選択することができないという課題があった。また、ステンシル方式を選択したほうがより高速な処理を行うことができる多角形である場合にも三角形分割方式などを選択してしまい、処理の負担が増加するという課題もあった。
【０００５】
この発明は上記のような課題を解決するためになされたもので、目的とする多角形の形状に応じた高速な描画を行うことができる描画装置を得ることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る描画装置は、描画対象の多角形を特定する頂点データに基づき変曲点を検出し、前記多角形はＹ軸座標が単調増加あるいは単調減少するｙ単調多角形であるか否か判定する多角形形状判定部と、前記多角形がｙ単調多角形である場合に、前記頂点データに基づき前記多角形内を複数の三角形に分割して三角形分割データを生成する三角形分割部と、前記多角形がｙ単調多角形でない場合に、頂点の描画順序に基づき前記多角形をステンシル方式で描画してステンシルデータを生成するステンシル処理部と、前記三角形分割データおよび前記ステンシルデータに基づき、描画箇所を特定箇所に制限するマスクパターンを作成するマスク作成部と、前記多角形に外接する矩形であるバウンディングボックスを用いて、前記マスクパターンの上から前記多角形の塗りつぶしを行い描画する描画部と、前記描画された多角形を外部装置に出力する表示処理部とを備えるものである。
【発明の効果】
【０００７】
この発明によれば、多角形形状判定部が描画対象の多角形を特定する頂点データに基づき変曲点を検出し、前記多角形はＹ軸座標が単調増加あるいは単調減少するｙ単調多角形であるか否か判定し、前記多角形がｙ単調多角形である場合に、三角形分割部が前記頂点データに基づき前記多角形内を複数の三角形に分割して三角形分割データを生成し、前記多角形がｙ単調多角形でない場合に、ステンシル処理部が頂点の描画順序に基づき前記多角形をステンシル方式で描画してステンシルデータを生成するように構成したので、目的とする多角形の形状を判断し、当該形状に応じて最も処理速度が高速となる描画処理方法を選択することができる。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
図１は、この発明の実施の形態１に係る描画装置の構成を示すブロック図である。
描画装置１は、主に、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）またはＭＰＵ（Ｍｉｃｒｏ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）で構成される描画処理部２およびプログラム３１を有するメモリ３で構成されている。また、この描画装置１はＩ／Ｏインタフェース４を介して記憶装置５や表示装置６と接続されている。記憶装置５は、描画対象となる多角形を特定する複数の多角形データを格納している。表示装置６は、描画装置１において描画された多角形を画面上などに表示する。
【０００９】
描画処理部２は、頂点データ記憶部２１、多角形形状判定部２２、三角形分割部２３、ステンシル処理部２４、マスク作成部２５、描画部２６および表示処理部２７を備えている。頂点データ記憶部２１は、Ｉ／Ｏインタフェース４を介して記憶装置５から多角形データを読み出し、この多角形データから多角形の各頂点座標を取得して記憶する。多角形形状判定部２２は、頂点データ記憶部２１に記憶された頂点座標を用いて、描画対象の多角形が変曲点を有するか否か判定する変曲点検出処理を行う。変曲点を有しない場合にはｙ単調な多角形であると判断し、その後の処理を三角形分割方式へ分岐する。一方、変曲点を有する場合にはｙ単調でない多角形であると判断し、その後の処理をステンシル方式へ分岐する。
【００１０】
ここで、図２および図３を用いて変曲点、接続点、ｙ単調な多角形およびｙ単調でない多角形について説明を行う。図２は多角形における変曲点と接続点を示す図であり、図３（ａ）はｙ単調な多角形を示し、図３（ｂ）はｙ単調でない多角形を示す図である。
まず、変曲点とは、注目する頂点の両側に位置する隣接点が共にＹ軸方向において注目頂点の上方に位置し、その注目頂点の内角が１８０°以上ある点（結合点）、および隣接点が共にＹ軸方向において注目頂点の下方に位置し、その注目頂点の内角が１８０°以上ある点（分離点）をいう。
【００１１】
図２の例では、注目頂点をＡ3とした場合、Ａ3の両側に位置する隣接点（Ａ2，Ａ4）が共にＹ軸方向においてＡ3よりも下方に位置し、Ａ3の内角が１８０°以上であることからＡ3は変曲点であると判断される。また、注目頂点をＡ10とした場合、Ａ10の両側に位置する隣接点（Ａ9，Ａ11）が共にＹ軸方向においてＡ10よりも上方に位置し、Ａ10の内角が１８０°以上であることからＡ10は変曲点であると判断される。一方、注目頂点をＡ1とした場合、Ａ1の両側に位置する隣接点（Ａ2，Ａ11）は、Ｙ軸方向においてＡ1に対してＡ2が下方に位置し、Ａ11が上方に位置し、内角が１８０°以下であることからＡ1は変曲点ではなく接続点であると判断される。
【００１２】
次にｙ単調な多角形およびｙ単調でない多角形について具体例を挙げて説明する。
ｙ単調な多角形とは、変曲点を有さずＹ軸座標が単調増加あるいは単調減少する多角形であり、例えば図３（ａ）に示すように、Ｙ軸座標の最大値を取る頂点Ｂ1から最小値を取る頂点Ｂ5に向かう際に、Ｙ軸方向に一度も上昇することなく常に下向きあるいは水平方向に進んでいく多角形をいう。一方、Ｙ単調でない多角形とは、図３（ｂ）に示すように、Ｙ軸座標の最大値を取る頂点Ｂ1から最小値を取る頂点Ｂ5に向かう際に、Ｙ軸方向に上がる点（Ｂ3´，Ｂ4´）を有する多角形をいう。
【００１３】
三角形分割部２３は、多角形形状判定部２２の判定結果に基づき、描画対象の多角形の１つの頂点を注目点とし、スタックされた他の頂点に向けて対角線を形成する処理を繰り返して多角形を複数の三角形に分割した三角形分割データを生成する。ステンシル処理部２４は、多角形形状判定部２２の判定結果に基づき、多角形の頂点の描画順に従って形成される三角形を描画してステンシルデータを生成する。マスク作成部２５は、三角形分割部２３から入力される三角形分割データとステンシル処理部２４から入力されるステンシルデータに基づく図形のマスクパターンを作成し、このマスクパターンをステンシルバッファ２５ａに格納する。
【００１４】
ここでマスクパターンとは、図形の描画箇所を特定部分に制限するものである。このマスクパターンにより、図形全体の塗りつぶしを行ったとしても描画可能箇所のみを描画することができる。図４にマスクパターンの具体例を示す。（ａ）は星型の図形を有するマスクパターンであり、（ｂ）は図形を塗りつぶすカラーバッファを示している。（ａ）のマスクパターンに（ｂ）のカラーバッファを通すことにより、（ｃ）に示すようなカラーバッファの色彩で塗りつぶされた星型を描画することができる。
【００１５】
描画部２６は、ステンシルバッファ２５ａに格納されたマスクパターンを通して描画対象である多角形の塗りつぶしを行う。表示処理部２７は、描画部２６において塗りつぶされた多角形の描画データに対して表示処理を行う。
【００１６】
次に、描画装置１の動作について説明する。図５は、実施の形態１に係る描画装置の動作を示すフローチャートである。
描画装置１においてメモリ３のプログラム３１の実行が開始されると、描画処理部２の頂点データ記憶部２１は、記憶装置５から必要な数だけ多角形データを読み出して取得する（ステップＳＴ１）。なお、この動作説明では一つの多角形データを取得するものとして説明する。さらに頂点データ記憶部２１は、取得した多角形データに基づき描画対象の多角形の各頂点座標（Ｖ１〜Ｖｎ）を取得して記憶する（ステップＳＴ２）。
【００１７】
多角形形状判定部２２は、ステップＳＴ２において頂点データ記憶部２１に記憶された角頂点の座標情報（Ｖ１〜Ｖｎ）を読み出し、読み出した座標情報に基づき変曲点の検出を行う（ステップＳＴ３）。さらにステップＳＴ３の検出結果に基づき描画対象の多角形がｙ単調多角形であるか否か判定を行う（ステップＳＴ４）。ステップＳＴ４において多角形が変曲点が検出されずｙ単調多角形であると判定された場合には、多角形データは三角形分割部２３に出力され、三角形分割方式処理が行われる（ステップＳＴ５）。一方、ステップＳＴ４において変曲点が検出されｙ単調多角形でないと判定された場合には、多角形データはステンシル処理部２４に出力され、ステンシル方式処理が行われる（ステップＳＴ６）。三角形分割方式処理およびステンシル方式処理の詳細については後述する。
【００１８】
マスク作成部２５は、ステップＳＴ５において生成された三角形分割データと、ステップＳＴ６において生成されたステンシルデータに基づき、描画対象の多角形のマスクパターンを生成し、ステンシルバッファ２５ａに格納する（ステップＳＴ７）。描画部２６は、ステップＳＴ７において格納されたマスクパターンを用いて塗りつぶしを行い、描画対象の多角形の描画を行う（ステップＳＴ８）。表示処理部２７は、ステップＳＴ８において描画された多角形の描画データに対して表示処理を行い、Ｉ／Ｏインタフェース４を介して表示装置６に出力してディスプレイなどに出力し（ステップＳＴ９）、処理を終了する。
【００１９】
次に、三角形分割方式処理の詳細について、図６および図７に基づき説明する。図６は実施の形態１に係る描画装置の三角形分割部の動作を示すフローチャートであり、図５において示した三角形分割方式処理ＳＴ５の内容を詳細に説明したものである。図７は、三角形分割方式処理の具体例を示す説明図である。
まず、図６のフローチャートに従って三角形分割部の動作の説明を行う。
三角形分割部２３は、描画対象の多角形の各頂点の配列をＹ軸座標の降順にソートする（ステップＳＴ１１）。ステップＳＴ１１においてソートされた頂点配列のうち先頭から２頂点分を内部メモリ（図示せず）などにスタックする（ステップＳＴ１２）。注目点Ｐｎを先頭から３番目（ｎ＝３）の頂点に設定する（ステップＳＴ１３）。
【００２０】
注目点Ｐｎ（ｎ＝３）から、ステップＳＴ１２においてスタックされた頂点に向けて多角形の内側に形成することができる対角線を引く（ステップＳＴ１４）。次に、多角形内を全て三角形に分割したか否か判定する（ステップＳＴ１５）。ステップＳＴ１５において、多角形内を全て三角形に分割できていないと判定された場合には、ステップＳＴ１４において分割されなかった頂点を全てスタックし（ステップＳＴ１６）、注目点Ｐｎを一つずらし（ｎ＝ｎ＋１）（ステップＳＴ１７）、ステップＳＴ１４の処理に戻り上述した処理を繰り返す。一方、ステップＳＴ１５において、多角形内を全て三角形に分割したと判定された場合には、三角形分割方式処理を終了して図５のメインフローのステップＳＴ７の処理に進む。
【００２１】
次に、図６のフローチャートの流れに沿って、図７に示す多角形を用いて三角形分割部の具体的な動作説明を行う。
まず、ステップＳＴ１１として、多角形の各頂点の配列をＹ軸座標の降順、即ち頂点Ｃ1，Ｃ2，Ｃ3，Ｃ4，Ｃ5，Ｃ6，Ｃ7の順にソートする。ステップＳＴ１２および１３として、ソートされた頂点配列の先頭から２頂点分の頂点Ｃ1およびＣ2をスタックし、注目点Ｐｎを先頭から３番目の頂点Ｃ3に設定する（Ｐｎ＝Ｃ3）。ステップＳＴ１４として注目点Ｃ3から、ステップＳＴ１２においてスタックされた頂点Ｃ1およびＣ2に向けて多角形の内側に形成することができる対角線を引く。ステップＳＴ１５として多角形内を全て三角形に分割したか否か判定する。
【００２２】
図７の例では全て三角形に分割できていない多角形Ｃ2Ｃ3Ｃ4Ｃ5Ｃ6Ｃ7が存在するため、ステップＳＴ１６としてステップＳＴ１２において分割されなかった頂点Ｃ4，Ｃ5，Ｃ6，Ｃ7をスタックする。また、ステップＳＴ１７として注目点Ｃ3を一つずらしてＣ4に設定し、ステップＳＴ１４´として新たにスタックされた頂点Ｃ5，Ｃ6，Ｃ7に向けて多角形の内側に形成することができる対角線を引く。ステップＳＴ１５´として多角形内を全て三角形に分割したか否か再度判定する。
【００２３】
図７の例では全て三角形に分割できていない多角形Ｃ2Ｃ3Ｃ4Ｃ5が存在するため、ステップＳＴ１６´としてステップＳＴ１６において分割されなかった頂点Ｃ2，Ｃ3をスタックする。また、ステップＳＴ１７´として注目点Ｃ4を一つずらしてＣ5に設定し、ステップＳＴ１４´´として新たにスタックされた頂点Ｃ2，Ｃ3に向けて多角形の内側に形成することができる対角線を引く。ステップＳＴ１５´´として多角形内を全て三角形に分割したか否か判定し、図７の例では多角形を全て三角形に分割できているため三角分割方式処理を終了する。
【００２４】
次に、ステンシル方式処理の詳細について、図８および図９に基づき説明する。図８は実施の形態１に係る描画装置のステンシル処理部の動作を示すフローチャートであり、図５において示したステンシル方式処理ＳＴ６の内容を詳細に説明したものである。図９は、ステンシル方式処理の具体例を示す説明図である。
まず、図８のフローチャートに従ってステンシル処理部の動作の説明を行う。
ステンシル処理部２４は、描画対象の多角形の各頂点の配列のうち先頭の頂点を開始点Ｐｆとして登録する（ステップＳＴ２１）。ステップＳＴ２１において登録された開始点Ｐｆからその他の各頂点に対して対角線を引いて三角形を形成する（ステップＳＴ２２）。ステップＳＴ２２において形成した三角形が、奇数回重なった部分のみを描画可能領域として（ステップＳＴ２３）ステンシル方式処理を終了し、図５のメインフローのステップＳＴ７の処理に進む。
【００２５】
次に、図８のフローチャートの流れに沿って、図９に示す多角形を用いてステンシル処理部の具体的な動作説明を行う。
まず、ステップＳＴ２１として、多角形の各頂点の配列のうち先頭の頂点Ｄ1を開始点Ｐｆとして登録する。ステップＳＴ２２として、開始点Ｄ１からその他の頂点Ｄ2からＤ10に対して対角線を引き三角形を形成する。具体的には、（ａ）の三角形「Ｄ1Ｄ2Ｄ3」、（ｂ）の三角形「Ｄ１Ｄ３Ｄ４」、（ｃ）の三角形「Ｄ1Ｄ5Ｄ6」、（ｄ）の三角形「Ｄ1Ｄ6Ｄ7」、（ｅ）の三角形「Ｄ1Ｄ8Ｄ9」、（ｆ）の三角形「Ｄ1Ｄ9Ｄ10」を形成する。
【００２６】
ステップＳＴ２３として、ステップＳＴ２２において形成された三角形が奇数回重なった部分のみ、即ち三角形が偶数回重なった三角形「Ｄ1Ｄ2Ｄ3」および「Ｄ1Ｄ9Ｄ10」である描画不可能領域を除いたその他全ての三角形を、描画可能領域として処理を終了する。ステップＳＴ２１からステップＳＴ２３の処理により、（ｆ）に示す星型の描画領域を得ることができる。
【００２７】
以上のように、この実施の形態１によれば、描画対象の多角形がｙ単調多角形であるか否か判定し、判定結果に基づき多角形の描画処理を三角形分割方式処理あるいはステンシル方式処理に分岐する多角形形状判定部２２を設けるように構成したので、多角形の形状に応じて最も高速な描画処理方法を選択することができる。
【００２８】
また、現行の携帯電話やカーナビゲーションシステムなどは３Ｄグラフィックス用ハードウェアを有するものが多く、この実施の形態１による三角形分割方式やステンシル方式は、この３Ｄグラフィックスの機能によりサポートされているため、携帯電話やカーナビゲーションシステムの３Ｄグラフィックス用アクセラレータを利用することができ有効である。
【００２９】
実施の形態２．
実施の形態１において示したステンシル方式処理では、図８のフローチャートのステップＳＴ２２の処理において、目的とする描画対象の多角形外に不要な塗りつぶし部分が発生し、処理に負担がかかる。具体例を挙げて説明すると、図１０（ａ）に示す多角形において実施の形態１のステンシル方式処理を施すと、多角形Ｅ1Ｅ2Ｅ3Ｅ4Ｅ5Ｅ6Ｅ7を塗りつぶす際に、この多角形外の３箇所の三角形部分「Ｅ1Ｅ2Ｅ3」、「Ｉ1Ｅ4Ｅ5」および「Ｅ1Ｅ6Ｅ7」に無駄な塗りつぶし処理が発生している。
【００３０】
この実施の形態２では、上述したステンシル方式処理における無駄な塗りつぶし処理を抑制する構成について示す。図１１は、実施の形態２に係る描画装置の構成を示すブロック図である。この描画装置１は、実施の形態１において示したステンシル処理部２４に重心算出部２４ａを追加して設けている。以下では、実施の形態１に係る描画装置１の構成要素と同一または相当する部分には、実施の形態１で使用した符合と同一の符号を付して説明を省略または簡略化する。
【００３１】
ステンシル処理部２４の重心算出部２４ａは、描画対象の多角形の各頂点座標を用いて当該多角形の重心を算出する。ステンシル処理部２４は、重心算出部２４ａにおいて算出された多角形の重心を開始点に設定してステンシル方式処理を行う。
【００３２】
次に、実施の形態２に係る描画装置のステンシル処理部の動作について説明する。図１２は実施の形態２に係るステンシル処理部の処理動作を示すフローチャートであり、以下このフローチャートに従って説明する。
ステンシル処理部２４の重心算出部２４ａは、描画対象の多角形の各頂点座標から重心  を算出する（ステップＳＴ３１）。ステンシル処理部２４は、ステップＳＴ３１において算出された重心を開始点Ｐｆとして登録する（ステップＳＴ３２）。さらに、ステップＳＴ３２において登録された開始点Ｐｆからその他の各頂点に対して対角線を引いて三角形を形成する（ステップＳＴ２２）。ステップＳＴ２２において形成した三角形が、奇数回重なった部分のみを描画可能領域として（ステップＳＴ２３）ステンシル方式処理を終了し、図５のメインフローのステップＳＴ７の処理に進む。
【００３３】
図１２のフローチャートの流れに沿ってこの実施の形態２のステンシル処理部の処理を行った場合の具体例を図１０（ｂ）に示す。
重心Ｖ１´を開始点Ｐｆとして、多角形Ｅ2´Ｅ3´Ｅ4´Ｅ5´Ｅ6´Ｅ7´Ｅ8´に図１２に示したステンシル方式処理を施すと、多角形外に発生する不要な塗りつぶし部分が三角形「Ｉ2Ｅ2´Ｅ3´」、「Ｉ1Ｅ5´Ｅ6´」の２箇所のみとなる。図１０（ａ）で示した実施の形態１のステンシル方式処理と比較すると不要な塗りつぶし部分が減少しており、処理の負担を軽減することができる。
【００３４】
以上のように、この実施の形態２によれば、ステンシル処理部２４に多角形の重心を算出する重心算出部２４ａを設け、算出された多角形の重心を開始点としてステンシル処理を行うように構成したので、ステンシル方式処理のマスクパターン作成時におけるメモリ負荷を軽減することができ、より高速な描画が可能となる。
【００３５】
実施の形態３．
実施の形態３においても、ステンシル方式処理における無駄な塗りつぶし処理を抑制する構成について示す。図１３は、実施の形態３に係る描画装置の構成を示すブロック図である。この描画装置１は、実施の形態１において示したステンシル処理部２４にバウンディングボックス中点算出部２４ｂを追加して設けている。以下では、実施の形態１に係る描画装置１の構成要素と同一または相当する部分には、実施の形態１で使用した符合と同一の符号を付して説明を省略または簡略化する。
【００３６】
まず、図１４を用いてバウンディングボックスについて説明する。（ａ）は描画対象の多角形を示すマスクパターン、（ｂ）は表示画面全体の塗りつぶしを行うカラーバッファ、（ｃ）はバウンディングボックスのカラーバッファをそれぞれ示している。通常、マスクパターン（ａ）を用いて描画を行う場合には、マスクパターン（ａ）にカラーバッファ（ｂ）を用いて塗りつぶしを行う。しかし、実際に塗りつぶす必要がある領域はマスクパターンに形成された多角形の範囲のみであり、この多角形の領域で全て包含することができる。
【００３７】
そこで、マスクパターンに形成された多角形についてＸ軸およびＹ軸方向の最大値と最小値をあらかじめ格納しておき、この最大値と最小値を用いて多角形を内包することができる最小の矩形で形成されたカラーバッファ、即ちバウンディングボックスを用いて塗りつぶすことにより、塗りつぶしの無駄を抑制することができる。この実施の形態３では、バウンディングボックスの領域情報を用いてステンシル方式処理の不要な塗りつぶし処理を抑制する。
【００３８】
バウンディングボックス中点算出部２４ｂは、描画対象の多角形を内包する最小の矩形であるバウンディングボックスのＸ軸およびＹ軸方向の最大値と最小値を用いて、バウンディングボックスの中点を算出する。ステンシル処理部２４は、バウンディングボックス中点算出部２４ｂにおいて算出されたバウンディングボックスの中点を開始点に設定してステンシル方式処理を行う。
【００３９】
次に、実施の形態３に係る描画装置のステンシル処理部の動作について説明する。図１５は実施の形態３に係るステンシル処理部の処理動作を示すフローチャートであり、以下このフローチャートに従って説明する。
ステンシル処理部２４のバウンディングボックス中点算出部２４ｂは、描画対象の多角形を内包する最小の矩形であるバウンディングボックスの中点を算出する（ステップＳＴ４１）。ステンシル処理部２４は、ステップＳＴ４１において算出されたバウンディングボックスの中点を開始点Ｐｆとして登録する（ステップＳＴ４２）。さらに、ステップＳＴ４２において登録された開始点Ｐｆからその他の各頂点に対して対角線を引いて三角形を形成する（ステップＳＴ２２）。ステップＳＴ２２において形成した三角形が、奇数回重なった部分のみを描画可能領域として（ステップＳＴ２３）ステンシル方式処理を終了し、図５のメインフローのステップＳＴ７の処理に進む。
【００４０】
以上のように、この実施の形態３によれば、ステンシル処理部２４に描画対象の多角形を内包する最小の矩形であるバウンディングボックスの中点を算出するバウンディングボックス中点算出部２４ｂを設け、算出されたバウンディングボックスの中点を開始点としてステンシル処理を行うように構成したので、ステンシル方式処理のマスクパターン生成時におけるメモリ負荷を軽減することができ、より高速な描画が可能となる。
【００４１】
ただし、この実施の形態３の構成は、実施の形態２の多角形の重心を用いてステンシル処理を行う構成と比較すると、効率のよい塗りつぶしができるとはいえない。しかし、この実施の形態３の構成では目的とする多角形の塗りつぶしに用いるデータを利用しているため、セットアップコストがかからないという利点がある。
【図面の簡単な説明】
【００４２】
【図１】この発明の実施の形態１に係る描画装置の構成を示すブロック図である。
【図２】変曲点を示す説明図である。
【図３】ｙ単調な図形およびｙ単調でない図形を示す説明図である。
【図４】この発明の実施の形態１に係る描画装置の描画方法を示す図である。
【図５】この発明の実施の形態１に係る描画装置の動作を示すフローチャートである。
【図６】この発明の実施の形態１に係る描画装置の三角形分割部の動作を示すフローチャートである。
【図７】この発明の実施の形態１に係る描画装置の三角形分割方式処理を示す例である。
【図８】この発明の実施の形態１に係る描画装置のステンシル処理部の動作を示すフローチャートである。
【図９】この発明の実施の形態１に係る描画装置のステンシル方式処理を示す例である。
【図１０】この発明の実施の形態２に係る描画装置のステンシル方式処理を示す例である。
【図１１】この発明の実施の形態２に係る描画装置の構成を示すブロック図である。
【図１２】この発明の実施の形態２に係る描画装置のステンシル処理部の動作を示すフローチャートである。
【図１３】この発明の実施の形態３に係る描画装置の構成を示すブロック図である。
【図１４】バウンディングボックスを示す説明図である。
【図１５】この発明の実施の形態３に係る描画装置のステンシル処理部の動作を示すフローチャートである。
【符号の説明】
【００４３】
１  描画装置、２  描画処理部、３  メモリ、４  Ｉ／Ｏインタフェース、５  記憶装置、６  表示装置、２１  頂点データ記憶部、２２  多角形形状判定部、２３  三角形分割部、２４  ステンシル処理部、２４ａ  重心算出部、２４ｂ  バウンディングボックス中点算出部、２５  マスク作成部、２５ａ  ステンシルバッファ、２６描画部、２７  表示処理部、３１  プログラム。
【図１】
2010072808.tif 000003
【図２】
2010072808.tif 000004
【図３】
2010072808.tif 000005
【図４】
2010072808.tif 000006
【図５】
2010072808.tif 000007
【図６】
2010072808.tif 000008
【図７】
2010072808.tif 000009
【図８】
2010072808.tif 000010
【図９】
2010072808.tif 000011
【図１０】
2010072808.tif 000012
【図１１】
2010072808.tif 000013
【図１２】
2010072808.tif 000014
【図１３】
2010072808.tif 000015
【図１４】
2010072808.tif 000016
【図１５】
2010072808.tif 000017