(57)【特許請求の範囲】
【請求項１】
描画対象の少なくとも一つの図形に含まれる各辺を含む各線分について、前記各線分を延長した直線と複数の基準線のうち２つとの交点の位置を表す座標を入力する交点座標入力部と、
前記各線分に対応する交点に対して、前記少なくとも一つの図形への適用が指示された座標変換を適用して、変換後の座標を算出する交点座標変換部と、
前記各線分に対応する座標変換後の交点を結ぶ直線の方程式を求める直線決定部と、
前記各線分に対応して求められた直線の方程式に基づいて、前記少なくとも一つの図形の境界を決定する境界決定部と
を備えたことを特徴とする図形描画装置。
【請求項２】
請求項１に記載の図形描画装置において、
前記交点座標入力部は、前記少なくとも一つの図形の頂点を含む前記各線分の端点の座標に基づいて、前記各線分を延長した直線と複数の基準線のうち２つとの交点の座標を求める交点座標算出部を備えた
ことを特徴とする図形描画装置。
【請求項３】
請求項１に記載の図形描画装置において、
前記境界決定部は、
前記少なくとも一つの図形が多角形である場合に、前記多角形の各辺に対応して求められた直線の方程式を用いて、前記多角形の内部の点が満たすべき条件を設定する条件設定部と、
前記条件設定部によって設定された条件に基づいて、前記多角形が表示される表示画面に含まれる各画素が前記多角形の内側であるか否かを判定する条件判定部とを備えた
ことを特徴とする図形描画装置。
【請求項４】
描画対象の少なくとも一つの図形に含まれる各辺を含む各線分について、前記各線分を延長した直線と複数の基準線のうち２つとの交点の位置を表す座標の入力を受ける受付手順と、
前記各線分に対応する交点に対して、前記少なくとも一つの図形への適用が指示された座標変換を適用して、変換後の座標を算出する交点座標変換手順と、
前記各線分に対応する座標変換後の交点を結ぶ直線の方程式を求める直線決定手順と、
前記各線分に対応して求められた直線の方程式に基づいて、前記少なくとも一つの図形の境界を決定する境界決定手順と
を備えたことを特徴とする図形描画方法。
【請求項５】
請求項４に記載の図形描画方法において、
前記境界決定手順は、
前記少なくとも一つの図形が多角形である場合に、前記多角形の各辺に対応して求められた直線の方程式を用いて、前記多角形の内部の点が満たすべき条件を設定する条件設定手順と、
前記条件設定手順によって設定された条件に基づいて、前記多角形が表示される表示画面に含まれる各画素が前記多角形の内側であるか否かを判定する条件判定手順とを備えた
ことを特徴とする図形描画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータなどの表示画面に線分および多角形を表示させるための描画情報を生成する図形描画装置および図形描画方法に関する。
【背景技術】
【０００２】
線分を表示画面に表示させるための描画情報は、線分の端点の位置を示す情報とこれらの端点が直線によって結ばれていることを示す情報を含んでいる。また、三角形や矩形などの多角形を表示画面に表示させるための描画情報は、多角形の頂点の位置を示す情報とこれらの端点が直線によってどのように結ばれているかを示す情報を含んでいる。
【０００３】
そして、従来の図形描画装置では、描画された図形に対してアフィン変換などの座標変換を行う際は、まず、線分の端点や多角形の頂点についてそれぞれ座標変換が行われる。そして、変換後の端点や頂点を結ぶように、線分や多角形の辺を表す描画情報が生成される。
【０００４】
なお、座標変換後の画像において、座標変換によって変形した図形の内部に含まれる各画素の画像データを、座標変換処理を用いずに求める方法も提案されている(特許文献1参照)。この方法では、水平走査線と変形した図形の辺のうち２つとの交点を考え、これらの交点を結ぶ直線を逆変換した変換前直線上の各画素の画像データを、変換後の図形において、水平走査線上に位置する画素の画像データとして読み込む。この操作を、図形と交わる水平走査線それぞれについて、順次に行うことにより、図形の内部に含まれる各画素の画像データを得ている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−１０９４５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、従来の図形描画装置によって、複数の多角形や線分が組み合わせられた図形を座標変換した際に、座標変換の前後で多角形の辺および線分相互の位置関係が精密には保たれない場合がある。例えば、大きさの異なる２つの三角形が互いの底辺が接するように配置された図形を座標変換した場合に、これらの三角形の底辺の間に隙間や重なりが生じてしまう場合があった。
【０００７】
従来は、図形描画装置において、線分の端点や多角形の頂点の座標値を高精度で算出することにより、上述した隙間や重なりといった位置ずれの抑制が図られていた。しかしながら、座標算出のための数値演算精度を上げると、図形描画装置の回路規模の増大や処理時間の増大を招いてしまう。
【０００８】
本件開示の装置は、数値演算精度を上げずに、複数の図形を座標変換した際の図形相互の位置ずれを抑制する図形描画装置および方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した目的は、以下に開示する図形描画装置によって達成することができる。
【００１０】
一つの観点による図形描画装置は、描画対象の少なくとも一つの図形に含まれる各辺を含む各線分について、各線分を延長した直線と複数の基準線のうち２つとの交点の位置を表す座標を入力する交点座標入力部と、各線分に対応する交点に対して、少なくとも一つの図形への適用が指示された座標変換を適用して、変換後の座標を算出する交点座標変換部と、各線分に対応する座標変換後の交点を結ぶ直線の方程式を求める直線決定部と、各線分に対応して求められた直線の方程式に基づいて、少なくとも一つの図形の境界を決定する境界決定部とを備える。
【００１１】
また、一つの観点による図形描画方法は、描画対象の少なくとも一つの図形に含まれる各辺を含む各線分について、各線分を延長した直線と複数の基準線のうち２つとの交点の位置を表す座標の入力を受ける受付手順と、各線分に対応する交点に対して、少なくとも一つの図形への適用が指示された座標変換を適用して、変換後の座標を算出する交点座標変換手順と、各線分に対応する座標変換後の交点を結ぶ直線の方程式を求める直線決定手順と、各線分に対応して求められた直線の方程式に基づいて、少なくとも一つの図形の境界を決定する境界決定手順とを備える。
【発明の効果】
【００１２】
本件開示の装置によれば、数値演算精度を上げずに、複数の図形を座標変換した際の図形相互の位置ずれを抑制することができる。
【図面の簡単な説明】
【００１３】
【図１】図形描画装置の一実施形態を示す図である。
【図２】線分の延長線と基準線との交点を説明する図である。
【図３】線分と延長線との関係を説明する図である。
【図４】交点の座標変換と図形の座標変換との関係を説明する図である。
【図５】図形描画処理を表す流れ図である。
【図６】交点演算処理部の別実施形態を示す図である。
【図７】図形管理テーブルの例を示す図である。
【図８】交点演算処理部の動作を表す流れ図である。
【図９】図形描画装置の別実施形態を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面に基づいて、本発明の実施形態について詳細に説明する。
(実施形態１)
図１に、図形描画装置の一実施形態を示す。図１に示した図形描画装置１００は、多角形および線分を含む図形を表す頂点情報と図形についての座標変換を指示する座標変換指示との入力に応じて、座標変換後の図形を表す画像データを生成する。
【００１５】
頂点情報は、多角形の頂点および線分の端点の座標を示す頂点情報とこれらの頂点および端点を結んで形成される図形との関係を示す図形情報を含む。また、頂点情報は、多角形の頂点および線分の端点の表示色およびテクスチャを含む画素の表示属性を表す頂点パラメータを含む。なお、頂点パラメータは、利用者が個々の頂点について独自に定義したパラメータを含むことができる。
【００１６】
図形描画装置１１０は、交点座標入力部１０１と、交点演算処理部１１０と、頂点演算処理部２０１と、表示データ生成部２０２とを備えている。交点座標入力部１０１は、頂点情報に含まれる頂点座標を結んで生成される線分に対応して、後述する所定の基準線との交点を示す交点座標を入力する。交点演算処理部１１０は、交点座標入力部１０１から入力された各交点座標と座標変換指示とに基づいて、後述するようにして、各図形に対する座標変換処理を当該図形に対応する交点座標に基づいて行う。この交点演算処理部１１０では、後述するようにして、各図形の内部に含まれる範囲が特定される。また、頂点演算処理部２０１は、頂点座標と座標変換指示とに基づく座標変換結果を用いて、各図形内部に含まれる各画素対応の表示データを算出するための情報を生成する。そして、表示データ生成部２０２は、交点演算処理部１１０で特定された範囲について、頂点演算処理部２０１で求められた情報を適用し、各図形を表示するための表示データを生成する。生成された表示データは、表示制御部２１１に渡され、表示装置２１２による図形の表示処理に供される。
【００１７】
頂点演算処理部２０１は、頂点座標変換部２０３と、図形生成部２０４と、図形表示判定部２０５と、パラメータ情報生成部２０６とを備えている。頂点座標変換部２０３は、頂点情報に含まれる各頂点座標を座標変換指示に従って座標変換し、変換後の頂点座標を図形生成部２０４に渡す。頂点座標変換部２０３は、例えば、３行３列の行列式を用いた行列演算によるアフィン変換処理により、座標変換を行うことができる。図形生成部２０４は、頂点情報に含まれる図形情報に基づいて、変換後の頂点座標で示される頂点を結ぶ線分に対応する直線の方程式を求める。頂点演算処理部２０１では、図形生成部２０４で求められた直線の方程式によって特定される図形を座標変換後の図形として、以下の処理を行う。図形表示判定部２０５は、図形生成部２０４から座標変換後の図形に含まれる各線分に対応する直線の方程式の組を受け取り、これらの情報に基づいて、座標変換後の図形を表示するか否かを判定する。例えば、座標変換後の図形が表示装置２１２の表示領域内に含まれる場合など、表示する条件を満たしている場合に、図形表示判定部２０５は、その図形を表示する旨の表示図形情報を交点演算処理部１１０に通知する。なお、図形表示判定部２０５は、例えば、座標変換後の図形が表示装置２１２の表示画面外に位置する場合などに、その図形を表示対象から外す判定をすることができる。また、図形表示判定部２０５によって表示対象とされた図形に対応する頂点座標は、パラメータ情報生成部２０６に渡される。そして、パラメータ情報生成部２０６は、各図形に対応する頂点座標と頂点情報に含まれる対応する頂点パラメータとに基づいて、個々の図形内部に含まれる各画素における各パラメータを算出するためのパラメータ情報を生成する。パラメータ情報は、例えば、図形内部に含まれる各画素の座標の変化分に対応する各パラメータの増分と各パラメータのオフセット値とを含むことができる。
【００１８】
一方、図１に示した交点座標入力部１０１は、交点座標算出部１０２を備えている。また、交点演算処理部１１０は、交点座標変換部１０３と、直線決定部１０４と、境界決定部１０５とを備えている。
【００１９】
次に、交点演算処理部１１０により、図形を構成する各線分を延長した直線と所定の基準線との交点を用いて、図形の座標変換後の範囲を特定する処理について説明する。
【００２０】
図２に、線分の延長線と基準線との交点を説明する図を示す。図３に、線分と延長線との関係を説明する図を示す。
【００２１】
図２に示した例では、表示装置２１２の表示領域の境界を示す矩形の２組の辺に相当する直線を基準線Ｂ１，Ｂ２，Ｂ３，Ｂ４として用いている。また、図２に示した例では、三角形ＡＢＣの辺ＡＢ上に、三角形ＤＥＦが辺ＥＦを接するように配置されている。これらの三角形ＡＢＣおよび三角形ＤＥＦが座標変換の対象となる場合に、頂点Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの座標を含む頂点情報が、図形描画装置１００に入力される。なお、以下の説明では、各頂点および辺および線分と基準線との交点の座標は、例えば、表示領域の左下を原点とし、水平走査方向をＸ軸、垂直走査方向をＹ軸とする座標系に基づいて表される。
【００２２】
図１に示した交点座標算出部１０２は、頂点情報に含まれる各頂点の頂点座標に基づいて、これらの頂点に対応する辺を延長した直線と、上述した基準線Ｂ１，Ｂ２，Ｂ３，Ｂ４のうち２つとの交点座標を算出する。同様に、折れ線図形に含まれる各線分や独立した線分についても、それぞれの端点の座標に基づいて、上述した基準線Ｂ１，Ｂ２，Ｂ３，Ｂ４のうち２つとの交点座標が算出される。
【００２３】
図２に示した例では、三角形ＡＢＣの辺ＡＢの延長線Ｌ１と、三角形ＤＥＦの辺ＥＦの延長線とは一致しているので、それぞれの辺に対応する基準線との交点として同一の交点座標の組が得られる。
【００２４】
なお、図２に示した例において、三角形ＡＢＣの辺ＢＣおよび辺ＣＡに対応する延長線を符号Ｌ２，Ｌ３を付して示した。また、三角形ＤＥＦの辺ＤＥおよび辺ＦＤに対応する延長線を符号Ｌ４，Ｌ５を付して示した。更に、これらの延長線Ｌ１，Ｌ２，Ｌ３，Ｌ４，Ｌ５と上述した基準線Ｂ１，Ｂ２，Ｂ３，Ｂ４との２つの交点Ｐ１，Ｐ２を、それぞれ延長線を示す符号を括弧書きで付して示した。
【００２５】
また、図２に示した各辺および線分と各延長線および各延長線と２つの基準線との交点との関係を、図３の表にまとめて示した。図３の例では、各延長線と２つの基準線との交点は、交点１欄と交点２欄とにそれぞれ示されている。
【００２６】
このようにして算出された各交点座標は、交点座標変換部１０３に入力される。また、頂点情報で指定された図形に対して任意の角度の回転や並進移動を行う旨の座標変換指示が交点座標変換部１０３に入力される。
【００２７】
このとき、交点座標変換部１０３は、交点座標算出部１０２から受け取った交点座標に対して、例えば、３行３列の行列式を用いた行列演算によるアフィン変換処理により、座標変換後の交点座標を算出する。
【００２８】
図４に、交点の座標変換と図形の座標変換との関係を説明する図を示す。図４の例は、図２に示した２つの三角形ＡＢＣおよび三角形ＤＥＦについて、点Ｑを中心として反時計回りに回転させる旨の座標変換指示に対応する行列演算の結果を示している。なお、図４において、図２に示した各延長線Ｌ１〜Ｌ５に対応する交点Ｐ１，Ｐ２に対応する座標変換後の点を、それぞれの延長線を括弧書きで付した符号Ｐ’１，Ｐ’２で示した。
【００２９】
そして、図４に、それぞれ網掛けを付して示すように、座標変換後の各交点を結ぶ直線に囲まれた領域として、座標変換後の図形を表すことができる。つまり、座標変換後の交点Ｐ’１(Ｌ１)，Ｐ’２(Ｌ１)を結ぶ直線Ｌ’１と、座標変換後の交点Ｐ’１(Ｌ２)，Ｐ’２(Ｌ２)を結ぶ直線Ｌ’２と、座標変換後の交点Ｐ’１(Ｌ３)，Ｐ’２(Ｌ３)を結ぶ直線Ｌ’３とが囲む領域として、座標変換後の三角形ＡＢＣを表すことができる。そして、同様に、座標変換後の交点Ｐ’１(Ｌ４)，Ｐ’２(Ｌ４)を結ぶ直線Ｌ’４と、座標変換後の交点Ｐ’１(Ｌ１)，Ｐ’２(Ｌ１)を結ぶ直線Ｌ’１と、座標変換後の交点Ｐ’１(Ｌ５)，Ｐ’２(Ｌ５)を結ぶ直線Ｌ’５とが囲む領域として、座標変換後の三角形ＤＥＦを表すことができる。
【００３０】
図４に示した例では、座標変換後の三角形ＡＢＣの辺ＡＢに対応する境界と、座標変換後の三角形ＤＥＦの辺ＥＦに対応する境界とは、同一の直線Ｌ’１によって示されている。したがって、座標変換後の三角形ＡＢＣの辺ＡＢと、座標変換後の三角形ＤＥＦの辺ＥＦとは、演算精度にかかわらず、同一直線上に配置されることが保証される。
【００３１】
故に、上述したように、各辺の延長線と所定の基準線との交点を座標変換して、この座標変換後の交点を結ぶ直線で囲まれる領域として図形を表すことにより、座標変換の前後で、図形相互の位置関係の変動を防ぐことができる。これにより、座標演算の精度を上げることなく、座標変換後に図形の間に意図しないスリットや重なりが生じることを防止できる。
【００３２】
図１に示した直線決定部１０４では、交点座標変換部１０３で得られた座標変換後の交点座標を、図形表示判定部２０５から通知された情報に基づいて組み合わせ、表示対象として指定された図形の座標変換後の辺に対応する直線の方程式を決定する。
【００３３】
また、境界決定部１０５は、直線決定部１０４で求められた直線の方程式を、図形表示判定部２０５から通知された情報に基づいて組み合わせ、表示対象として指定された座標変換後の図形に対応する画像データの範囲の境界を決定する。
【００３４】
このようにして決定された範囲の内部に含まれる画素について、表示データ生成部２０２により、各画素の表示のための表示データの生成が行われる。
【００３５】
次に、表示データ生成部２０２の処理内容とともに、図形描画装置全体の動作を説明する。
図５に、図形描画処理を表す流れ図を示す。図５に示した例では、交点演算処理部１１０による交点演算処理を破線で囲んで示した。
【００３６】
図形描画装置１００に頂点情報と座標変換指示とが入力されると(ステップ３０１)、まず、交点算出部１０２により、頂点情報で示される各線分と上述した基準線との交点が求められる(ステップ３０２)。このとき、交点算出部１０２は、各線分についてそれぞれを延長した直線の方程式を求め、この直線の方程式と図２に示した４つの基準線Ｂ１，Ｂ２，Ｂ３，Ｂ４に対応する直線の方程式とに基づいて、各線分と基準線との交点を求めることができる。
【００３７】
次いで、交点座標変換部１０３は、交点算出部１０２によって算出された各交点の座標に対して、例えば、座標変換指示に対応する行列演算を行うことにより、座標変換後の交点座標を求める(ステップ３０３)。
【００３８】
座標変換後の交点座標と図形表示判定部２０５から通知された情報とに基づいて、直線決定部１０４により、表示対象として指定された図形の座標変換後の辺に対応する直線の方程式が決定される(ステップ３０４)。図形表示判定部２０５から通知される情報には、例えば、表示対象の図形に含まれる各辺を特定する情報が含まれる。直線決定部１０４は、この情報に基づいて、各辺に関連付けられた座標変換後の交点座標を選択し、選択した交点座標を結ぶ直線の方程式を求めることができる。図４に示した例では、直線決定部１０４により、直線Ｌ’１〜Ｌ’５の方程式Ｅ１(ｘ，ｙ)〜Ｅ５(ｘ，ｙ)がそれぞれ求められる。
【００３９】
そして、これらの直線Ｌ’１〜Ｌ’５の方程式と図形表示判定部２０５から通知された情報とに基づいて、境界決定部１０５により、表示対象の図形それぞれに対応する範囲の境界が決定される(ステップ３０５)。図４に示した例では、各三角形の頂点は、時計回りに配置されている。この場合に、座標変換後の三角形ＡＢＣに対応する範囲は、座標変換後の三角形ＡＢＣの辺ＡＢ、辺ＢＣ，辺ＣＡにそれぞれ対応する直線の方程式Ｅ１(ｘ，ｙ)、Ｅ２(ｘ，ｙ)、Ｅ３(ｘ，ｙ)を用いて、式(１)のように表される。
【００４０】
｛Ｅ１(ｘ，ｙ)＞０｝＆｛Ｅ２(ｘ，ｙ)＞０｝＆｛Ｅ３(ｘ，ｙ)＞０｝・・・（１）
この式(１)の条件を満たす座標値で示される画素を抽出することにより、各辺の延長と基準線との交点を座標変換して得られる座標変換後の三角形ＡＢＣ内部に位置する画素をもれなく抽出することができる。
【００４１】
また、座標変換後の三角形ＤＥＦに対応する範囲は、辺ＤＥ、辺ＥＦ，辺ＦＤにそれぞれ対応する座標変換後の直線の方程式Ｅ４(ｘ，ｙ)、Ｅ１(ｘ，ｙ)、Ｅ５(ｘ，ｙ)を用いて、同様に表される。そして、この範囲に含まれる画素を抽出することにより、各辺の延長と基準線との交点を座標変換して得られる座標変換後の三角形ＤＥＦ内部に位置する画素をもれなく抽出することができる。
【００４２】
このようにして求められた表示対象の各図形の内部の画素は、座標変換前に各図形の内部の画素が分布していた範囲相互の位置関係を維持して分布している。そして、図２に示したように、２つの三角形ＡＢＣと三角形ＤＥＦとの境界が１つの直線で表されている場合には、座標変換後においても、２つの三角形の境界は、元の直線を座標変換した直線となっている。したがって、座標変換後の２つの三角形の間に意図しない隙間や重なりが表れることはない。
【００４３】
このようにして抽出された各図形の内部に含まれる各画素の表示データは、次のようにして生成される。
【００４４】
まず、頂点座標変換部２０３により、頂点情報に含まれる各頂点座標についての座標変換が行われる(ステップ３０６)。つづいて、図形生成部２０４により、座標変換後の頂点座標が図形と関連付けられる。また、図形表示判定部２０５により、座標変換によって表示領域の外側に移動した図形などが、表示対象の図形から除外される。そして、図形表示判定部２０５により、表示対象として残された各図形について、座標変換後の頂点座標と各頂点と図形との関連を示す情報とが生成され、これらの情報がパラメータ情報生成部２０６に渡される。
【００４５】
パラメータ情報生成部２０６は、図形表示判定部２０５からの情報とともに、頂点情報に含まれる頂点パラメータを受け取る。そして、これらの情報に基づいて、各図形の内部に位置する各画素の座標(ｘ、ｙ)について、各パラメータの値を求めるためのパラメータ情報を算出する(ステップ３０７)。例えば、パラメータ情報生成部２０６は、パラメータの種類ごとに、頂点座標における当該パラメータの値Ｓに相当するオフセット値Ｖｏｆと、ｘ、ｙ方向の座標値がそれぞれ１画素分増大した際の当該パラメータ値の増分ｄｓｄｘ、ｄｓｄｙを算出することができる。このようにして各パラメータについて求められたオフセット値Ｖｏｆとパラメータ値の増分ｄｓｄｘ、ｄｓｄｙとを含むパラメータ情報は、表示データ生成部２０２に渡される。
【００４６】
図１に示した表示データ生成部２０２は、パラメータ算出部２０７と、画素データ算出部２０８と、画素表示判定部２０９とを備えている。
【００４７】
パラメータ算出部２０７は、上述したステップ３０５で座標変換後の図形の内部に含まれる画素として抽出された各画素の座標に対応する各パラメータ値Ｓ(ｘ，ｙ)を、例えば、下の(２)式に基づいて算出する(ステップ３０８)。
【００４８】
Ｓ（ｘ，ｙ）＝ｄｓｄｘ＊ｘ＋ｄｓｄｙ＊ｙ＋Ｖｏｆ    ・・・（２）
このようにして求められた各パラメータ値に基づいて、画素データ算出部２０８は、座標変換後の各図形の内部に含まれる各画素(ｘ、ｙ)の表示色を表す画素データを算出する(ステップ３０９)。次いで、画素表示判定部２０９は、座標変換後の各図形の内部に含まれる各画素(ｘ、ｙ)について、ステンシルテストなどの画素ごとに表示／非表示を判定する処理を行う。そして、この判定処理で非表示と判定された画素を除く各画素の画素データが、表示制御部２１１に渡され、図形描画処理は終了される。
【００４９】
図１に示したように構成された図形描画装置１００によれば、座標変換の前後で変換対象の図形相互に位置ずれが発生することはない。一方、この図形描画装置１００に備えられる頂点座標変換部２０３および交点座標変換部１０３における演算精度は、従来の図形描画装置１００における座標値の演算精度と同等で十分である。つまり、図１に示したように構成された図形描画装置１００によれば、座標値の演算精度を上げずに、複数の図形を座標変換した際の図形相互の位置ずれを抑制することができる。
【００５０】
なお、図１に示した構成では、図５において破線で囲んで示した交点演算処理部１１０による処理と、頂点演算処理部２０１によって行われる処理(ステップ３０６，３０７参照)とを並行して実行することができる。このような並行処理を適用することにより、交点演算処理部１１０を適用した図形描画装置１００全体としての描画処理時間を、頂点座標に基づく座標変換のみを用いる場合と同等に抑えることができる。
【００５１】
また、図２に示したように、表示領域の境界に対応して複数の基準線を設定したことにより、描画対象の図形に含まれる各辺の延長線と基準線との交点を算出する処理を簡易化することができる。なお、複数の基準線は、表示領域内に描画される任意の図形に含まれる線分の延長と、複数の基準線に含まれる２つが交差するように設定することができる。このような基準線の組み合わせとしては、上述した表示領域の境界に対応して設定される基準線の組のほかに、表示領域に外接する三角形を構成する３つの辺に相当する直線の組が考えられる。
【００５２】
次に、上述した交点演算処理部１１０に備えられる直線決定部１０４および境界決定部１０５の具体的構成について説明する。
(実施形態２)
図６に、交点演算処理部の別実施形態を示す。なお、図６に示した構成要素のうち、図１に示した構成要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【００５３】
図６に示した直線決定部１０４は、図形情報管理部１１１と、図形管理テーブル１１２と、直線方程式算出部１１３とを備えている。また、境界決定部１０５は、条件設定部１１４と、条件判定部１１５とを備えている。
【００５４】
また、図７に、図形管理テーブルの例を示す。更に、図８に、交点演算処理部の動作を表す流れ図を示す。以下の説明では、図６、図７および図８を参照する。
【００５５】
図形情報管理部１１１は、交点座標算出部１０２による処理対象となった多角形の各辺および線分を示す線分ＩＤと、各線分に対応して算出された基準線との交点座標とを受け取り、これらを図形管理テーブル１１２に登録する(図８のステップ３１１)。図形情報管理部１１１は、例えば、線分ＩＤに対応して、２つの交点座標１，２を図形管理テーブル１１２に登録することができる。なお、図７に示した例では、図２に示した２つの三角形ＡＢＣと三角形ＤＥＦの各辺に対応して、それぞれの辺の延長線と基準線との交点座標が格納されている。また、図７の例では、各交点座標は、対応する延長線を示す番号と２つの交点を区別するための番号とを組み合わせた添え字を付して示されている。
【００５６】
次いで、ステップ３１２において、交点座標変換部１０３により、各交点についての座標変換が行われると、図形情報管理部１１１は、算出された座標変換後の交点座標を用いて、図形管理テーブル１１２の対応する交点座標を置き換える(ステップ３１３)。
【００５７】
そして、頂点演算処理部２０１から渡される表示図形情報に基づいて、図形情報管理部１１１は、図形管理テーブル１１２に登録された交点座標を、対応する線分が含まれている図形ごとに並べ替える(ステップ３１４)。図７に示した例では、辺ＡＢ，ＢＣ，ＣＡを示す線分ＩＤに対応して登録された３組の交点座標１，２が、三角形ＡＢＣに関連する情報としてまとめられている。同様に、辺ＤＥ，ＥＦ，ＦＤを示す線分ＩＤに対応して登録された３組の交点座標１，２は、三角形ＤＥＦに関連する情報としてまとめられる。
【００５８】
このようにして整理された図形管理テーブル１１２の情報に基づいて、直線方程式算出部１１３は、標示対象の図形に含まれる線分に対応して格納された２つの交点座標を結ぶ直線方程式を求める(ステップ３１５)。直線方程式算出部１１３は、例えば、辺ＡＢに対応する直線Ｌ１と基準線Ｂ１との交点座標１(Ｘ１１，Ｙ１１)と、基準線Ｂ３との交点座標２(Ｘ１２，Ｙ１２)とを結ぶ直線方程式Ｅ１（ｘ，ｙ）は、式(３)のように表される。
【００５９】
E1(x，y)＝(Y12−Y11)＊x−(X12−X11)＊y
−{X11＊(Y12−Y11)−Y11＊(X12−X11)}    ・・・（３）
直線方程式算出部１１３によって求められた直線方程式は、図形情報管理部１１１により図形管理テーブル１１２に格納される(ステップ３１６)。図７に示した例では、三角形ＡＢＣの辺ＡＢ上に三角形ＤＥＦの辺ＥＦが配置されていることが、これらの両辺に対応して同一の直線方程式Ｅ１(ｘ，ｙ)が格納されていることによって表されている。そして、この図形管理テーブル１１２は、条件設定部１１４による処理に供される。
【００６０】
条件設定部１１４は、表示図形情報で示された表示対象の図形に含まれる各辺に対応して、図形管理テーブル１１２に格納された直線方程式を用いて、図形内部に含まれる範囲を示す条件を設定する(ステップ３１７)。条件設定部１１４によって設定される条件は、実施形態１の説明において示した式(１)のように表すことができる。
【００６１】
そして、条件判定部１１５は、このようにして設定された条件に基づいて、表示対象の図形内部に含まれる画素を抽出し(ステップ３１８)、処理を終了する。例えば、条件判定部１１５は、表示領域内の各画素の座標について、順次に、各図形について設定された条件を満たすか否かを判定し、条件を満たす画素を表示データ生成部２０２に通知することができる。
【００６２】
このように、直線決定部１０４および境界決定部１０５の機能は、数値演算処理回路、論理演算処理回路および記憶素子を用いて実現することができる。
【００６３】
ところで、個々の図形は、複数の直線で囲まれる範囲として表すこともできる。したがって、上述した頂点情報に代えて、図形を複数の直線で囲まれる範囲として表す図形定義情報に基づいて、図形の描画を行う図形描画装置を構成することも可能である。
(実施形態３)
図９に、図形描画装置の別実施形態を示す。なお、図９に示した構成要素のうち、図１に示した構成要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【００６４】
図９に示した交点座標入力部１０１は、図１に示した交点座標算出部１０２とは異なる交点座標算出部１１６を備えている。この交点座標算出部１１６は、図形定義情報に基づいて、各図形の定義に用いられている各直線と上述した基準線との交点座標を算出する。
【００６５】
また、図９に示した直線決定部１０４は、交点座標変換部１０３によって得られた座標変換後の交点座標に基づいて、各図形の定義に用いられている各直線に対応する座標変換後の直線の方程式を求める。
【００６６】
図９に示した頂点演算処理部２０１は、頂点座標変換部２０３、図形生成部２０４に代えて、頂点座標算出部２１３および図形生成部２１４を備えている。頂点座標算出部２１３は、直線決定部１０４によって各図形の辺に対応して求められた各直線の方程式相互の交点を算出する。そして、算出した交点の座標を描画対象の各図形の頂点座標として図形生成部２１４に渡す。図形生成部２１４は、頂点座標算出部２１３から受け取った頂点座標および頂点座標の算出に用いられた各直線の方程式を、図形定義情報とに基づいて関連付けて、座標変換後の各図形を特定する情報を生成する。そして、この情報に基づいて、図形表示判定部２０５およびパラメータ情報生成部２０６の処理が行われる。
【００６７】
図９に示した構成では、図形生成部２１４によって特定される座標変換後の図形の辺は、直線決定部１０４によって座標変換後の各交点に基づいて求められた直線の方程式に基づいて特定されている。そして、これらの直線の交点座標が、図形生成部２１４によって特定される座標変換後の図形の頂点座標となる。
【００６８】
したがって、図９に示した構成では、パラメータ情報生成部２０６によって算出される各パラメータＳ(ｘ，ｙ)のオフセット値Ｖｏｆおよび増分ｄｓｄｘ、ｄｓｄｙにも、交点演算処理部１１０による演算結果が反映される。
【００６９】
なお、以上に説明した実施形態１、実施形態２および実施形態３に備えられる各部の機能は、同等の数値演算処理および論理演算処理を行うためのプログラムをコンピュータに実行させることによって実現することができる。
【符号の説明】
【００７０】
１００  図形描画装置
１０１  交点座標入力部
１０２．１１６  交点座標算出部
１０３  交点座標変換部
１０４  直線決定部
１０５  境界決定部
１１０  交点演算処理部
１１１  図形情報管理部
１１２  図形管理テーブル
１１３  直線方程式算出部
１１４  条件設定部
１１５  条件判定部
２０１  頂点演算処理部
２０２  表示データ生成部
２０３  頂点座標変換部
２０４，２１４  図形生成部
２０５  図形表示判定部
２０６  パラメータ情報生成部
２０７  パラメータ算出部
２０８  画素データ算出部
２０９  画素表示判定部
２１１  表示制御装置
２１２  表示装置
２１３  頂点座標算出部
【図１】
0005418310.tif 000002
【図２】
0005418310.tif 000003
【図３】
0005418310.tif 000004
【図４】
0005418310.tif 000005
【図５】
0005418310.tif 000006
【図６】
0005418310.tif 000007
【図７】
0005418310.tif 000008
【図８】
0005418310.tif 000009
【図９】
0005418310.tif 000010