JPH0567218A - 画素座標計算装置及びそれを用いた画像生成装置 - Google Patents

Abstract

(57)【要約】 【目的】 画素座標計算において、小さなポリゴンの場
合効率が悪いという課題を解決し、高速処理が可能な画
像生成装置を提供することを目的とする。。 【構成】 ポリゴン選択器１で、描画する複数のポリゴ
ンの中から第１の画素座標計算装置５で画素座標計算が
可能な小さなポリゴンを選択し、選択されたポリゴンに
ついては頂点座標変換器２と画素座標テーブル３と画素
座標変換器４で構成される第１の画素座標計算装置５
で、選択されなかったポリゴンについては第２の画素座
標計算装置６でそれぞれ画素座標を求め、それをもとに
画素データ演算器７で各画素の色や輝度計算を行い、そ
の演算結果をフレームメモリ８に格納する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータ・グラフ
ィックスにおける画素座標計算及びそれを用いた画像生
成装置に関するものである。

【０００２】

【従来の技術】近年、コンピュータ・グラフィック技術
の発展により、複雑な画像処理が可能になってきてい
る。ときにその処理精度、処理速度の改善について多く
の発明がなされている。従来のこの種のコンピュータ・
グラフィック技術により頂点座標が与えられた多角形画
像、いわゆるポリゴンの内部およびエッジの画素座標を
求める時、スキャン・ラインとよばれるＸ軸に平行な直
線とエッジとの交点を求め、これらの交点に囲まれたス
キャン・ライン上の画素を求めるという方法をとってき
た。これらの処理方法については、例えば、「コンピュ
ータ・グラフィックス」今宮淳美訳、日本コンピュータ
協会(１９８４年)などに詳しく述べられている。以下、
図４と図５を参照しながら、この従来の画素座標計算の
一例について説明する。

【０００３】図４に従来の画素座標計算装置の構成例を
示す。図４に示すようにその構成要素として４１はエッ
ジの傾き演算器で、ポリゴンの各頂点座標から各エッジ
の傾きを求めるものである。４２はエッジ上の画素座標
演算器で、ポリゴンの各頂点とエッジの傾きからエッジ
上の画素座標を求めるものである。４３はポリゴン内部
の画素座標演算器で、エッジ上の画素座標からポリゴン
内部の画素座標を求めるものである。一例として三角形
の頂点座標から内部の画素、およびエッジ上の画素座標
を求める方法を図５に示す。

【０００４】まず、エッジの傾き演算器４１で頂点５１
の座標と頂点５２の座標からエッジ５４の傾きを、頂点
５２の座標と頂点５３の座標からエッジ５５の傾きを、
頂点５３の座標と頂点５１の座標からエッジ５６の傾き
をそれぞれ求める。エッジ上の画素座標演算器４２で頂
点５１の座標とエッジ５４の傾きからエッジ５４上の画
素座標を、頂点５１の座標とエッジ５６の傾きからエッ
ジ５６上の画素座標を求める。エッジ５５上の画素座標
は、頂点５２の座標とエッジ５５の傾きから求められ
る。

【０００５】次に、内部画素座標演算器４３において、
ｙ座標値の等しいエッジ上の２点をむすぶ線分上の画素
座標を計算する。この線分をスキャンラインと呼ぶ。ス
キャン・ライン５７は、複数存在するスキャン・ライン
の中の１つを表す。画素５８、画素５９はそれぞれスキ
ャン・ライン５７とエッジ５４、エッジ５６との交点で
ある。画素６０、画素６１はともにスキャン・ライン５
７上の画素であり、三角形の内部の画素である。画素５
８と画素５９から画素６０と画素６１の座標が求められ
る。この処理をすべてのスキャン・ラインについて行う
ことにより、三角形の内部の画素座標が求められる。

【０００６】

【発明が解決しようとする課題】しかしながら前記のよ
うな構成では、ポリゴンの大きさにかかわらず、エッジ
上の画素座標を求めるまでに多くの乗除演算を必要なの
で演算に時間がかかり、とくに小さなポリゴンの場合
は、求める画素座標の個数が少ないのに非常に多くの計
算時間を費やすこととなり、効率が悪いという問題点を
有していた。

【０００７】本発明は上記課題に留意し、小さなポリゴ
ンに対してもエッジ上及びポリゴン内部の画素座標の算
出を効率的に高速に行うことができる画像生成装置を提
供することを目的とする。

【０００８】

【課題を解決するための手段】上記目的を達成するため
に、本発明の画素座標計算装置及びそれを用いた画像処
理装置は、ポリゴンの頂点の中から１点を基準点として
選び、この基準点以外の頂点座標を基準点からの相対座
標に変換する頂点座標変換器と、この頂点座標変換器が
出力する相対頂点座標からそのポリゴンの内部およびエ
ッジを構成する基準点からの相対画素座標を得るための
画素座標テーブルと、この相対画素座標を絶対画素座標
に変換する画素座標変換器という構成を備えたものであ
る。

【０００９】

【作用】上記構成の本発明の画素座標計算装置及びそれ
を用いた画像生成装置は、小さなポリゴンを描画する際
の画素座標を求めるために、ポリゴンの頂点座標とエッ
ジ及び内部の画素座標との対応を記述した画素座標テー
ブルを参照することにより、エッジの傾きやエッジ上の
画素座標計算などの計算を行う必要がなくなるものであ
る。

【００１０】

【実施例】以下本発明の一実施例の三角形の画素座標の
計算について、図面を参照しながら説明する。図１は本
発明の実施例における画像生成装置の構成を示すもので
ある。図１に示すようにその構成要素として１はポリゴ
ンの大小の選択を行うポリゴン選択器、２は頂点座標の
一つを基準点として相対座標に変換する頂点座標変換
器、３は相対画素座標とエッジ及びポリゴン内部の画素
の対応表である画素座標テーブル、４は相対画素座標を
絶対画素座標に変換する画素座標変換器、５は第１の画
素座標計算装置、６は第２の画素座標計算装置、７は画
素の色や輝度等を計算する画素データ演算器、８はフレ
ームメモリである。以上のように構成された画像生成装
置について、以下その動作を説明する。

【００１１】まず、全体の処理の流れについて説明す
る。ポリゴン選択器１は、描画する複数のポリゴンの中
から第１の画素座標計算装置で画素座標計算が可能な小
さなポリゴンを選択する。ポリゴン選択器１によって選
択されたポリゴンについては、その頂点座標値が第１の
画素座標計算装置５に入力され、選択されなかったポリ
ゴンの頂点座標値は第２の画素座標計算装置６に入力さ
れる。第２の画素座標計算装置６は従来の方法で画素座
標を計算する装置である。第１の画素座標計算装置５ま
たは第２の画素座標計算装置６から出力された画素座標
値は、画素データ演算器７に入力され各画素の色や輝度
計算を行い、その演算結果をフレームメモリ８に格納す
る。

【００１２】次に第１の画素座標計算装置５について説
明する。第１の画素座標計算装置５は頂点座標変換器２
と画素座標テーブル３と画素座標変換器４から構成され
る。頂点座標変換器２は、ポリゴンの頂点座標から１点
を基準点として選び、他の頂点座標を基準点からの相対
座標に変換する。画素座標テーブル３は頂点座標変換器
２で出力される座標値からテーブルを調べ、ポリゴンの
画素座標を求める。画素座標テーブル３で求められた画
素座標は、基準点からの相対座標なので、画素座標変換
器４は前記相対画素座標を絶対画素座標に変換する。三
角形の具体的な座標値を用いて画素座標計算過程を図２
に示す。図２（ａ）において、２１は描画する三角形の
絶対頂点座標を示す。頂点座標変換器２で３つの座標の
うちの１つである(２,３)を基準点として選んだ場合、
他の頂点座標(６,４)、(５,６)は、それぞれ図２（ｂ）
に示す２２の三角形の相対頂点座標(４,１)、(３,３)に
変換される。この三角形の相対頂点座標２２をもとに図
２（ｃ）に示す画素座標テーブル２３から２４の三角形
内部およびエッジの相対画素座標(１，０)、(０，１)、
(２，１)、(２，２)、(３，１)、(３，２)を得る。この
相対画素座標２４は画素座標変換器４によって、図２
（ｄ）に示す２５の絶対画素座標(３．３)、(２，４)、
(４，４)、(４，５)、(５，４)、(５，５)にそれぞれ変
換される。なお、図２では三角形の画素座標を求める場
合を例にして説明を行ったが、三角形以外のポリゴンに
ついても同様な方法で画素座標が計算される。

【００１３】次に、ポリゴン選択器１におけるポリゴン
選択方法について説明する。ポリゴン選択器１におい
て、ポリゴンの頂点のうち一つを基準点に選び、基準点
と他の任意の頂点座標とのｘ,ｙ座標の変位がいずれも
ｍ以下であるか否かでポリゴンを分類する。ｍは自然数
の定数である。ｍ＝３の場合の例を図３に示す。図３に
おいて◎印３１は基準点を表し、複数の○印３２は基準
点からｘ,ｙ座標の変位がいずれも３以下の画素を表
し、３３と３４は、ポリゴン選択器１に選択されるポリ
ゴンを表し、３５はポリゴン選択器１に選択されないポ
リゴンを表す。すなわち、ポリゴンの１頂点を基準点３
１をとしたとき、その他の頂点はすべて○印で示した画
素３２のうちのどれかであれば、そのポリゴンはポリゴ
ン選択器１によって選択される。

【００１４】ｍの値は画素座標テーブルの大きさに関係
する。例えば、三角形のみを扱う場合でｍ＝３と決定し
た場合について、画素座標テーブル３の大きさを考えて
みる。基準点とその他の画素の中の２点を頂点とする三
角形の場合の数は４８個ある画素３２の中から２個選ぶ
組合せであるから、直線になる場合も含めて１１２８通
りある。

【００１５】

【数１】

【００１６】この値から３点が直線上にならぶ場合の数
を引いた値が画素座標変換テーブル３のエントリー数に
相当する。従ってエントリー数は１１２８未満である。
次に一つの三角形を構成する画素数は、最も大きな三角
形で１５個(基準点を除く)であるから、テーブルの１エ
ントリーあたり１５個の画素座標を格納できる大きさを
用意すればよい。また、画素の総数は４９個であるから
一つの画素座標を表すのに６ビット用意すればよい。し
たがって、画素座標テーブル３の大きさは(数２)で計算
されるように、１２Ｋバイトあれば十分である。

【００１７】

【数２】

【００１８】(表１)にｍ＝３，４，５，６の場合につい
て前記の方法と同様に概算した座標変換テーブル３の大
きさを示す。画素座標テーブルに確保できるメモリの大
きさを考慮してｍの大きさを決定すれば、実現可能な画
素座標装置を作成することができる。

【００１９】

【表１】

【００２０】以上のように本実施例によれば、画素座標
テーブルを設けることによりポリゴン内部及びエッジの
画素座標を複雑な計算を行わずに求めることができる。

【００２１】

【発明の効果】以上の説明から明らかなように、本発明
の画素座標計算装置及びそれを用いた画像生成装置は、
画素座標の計算の際に画素座標テーブルを用いることに
より、小さなポリゴンに対して、そのポリゴンの内部お
よびエッジの画素座標を複雑な計算を行わずに求めるこ
とができるので効率的に画素座標計算が可能であり、高
速な画像処理が可能な画像生成が実現するものである。

【図面の簡単な説明】

【図１】本発明の実施例における画像生成装置の構成を
示すブロック図

【図２】同実施例における第１の画素座標計算装置で三
角形の画素座標を求める一例を示す説明図

【図３】同実施例におけるポリゴン選択器のポリゴン選
択方法の一例を示す説明図

【図４】従来の画素座標計算装置の構成を示すブロック
図

【図５】同従来の画素座標計算装置における画素座標を
求める一例を示す説明図

【符号の説明】

１ ポリゴン選択器 ２ 頂点座標変換器 ３ 画素座標テーブル ４ 画素座標変換器 ５ 第１の画素座標計算装置 ６ 第２の画素座標計算装置 ７ 画素データ演算器 ８ フレームメモリ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 ポリゴンの頂点の中から１点を基準点と
   して選び、前記基準点以外の頂点座標を前記基準点から
   の相対座標に変換する頂点座標変換器と、前記頂点座標
   変換器が出力する相対頂点座標から前記ポリゴンの内部
   およびエッジを構成する画素の基準点からの相対座標を
   得るための画素座標テーブルと、前記画素座標テーブル
   から得られた相対画素座標を絶対画素座標へ変換する画
   素座標変換器とを備えた画素座標計算装置。
2. 【請求項２】請求項１記載の画素座標計算装置から得ら
   れた画素座標の画素について、画素データを演算する画
   素データ演算器と、前記画素データ演算器の演算結果を
   格納するフレームメモリとを備えた画像生成装置。
3. 【請求項３】 ポリゴンの頂点の中から１点を基準点と
   して選び、前記基準点から前記基準点以外の任意の頂点
   座標への距離がある一定値以下のポリゴンを選択するポ
   リゴン選択器と、前記ポリゴン選択器に選択されたポリ
   ゴンに対して座標計算を行う請求項１記載の画素座標計
   算装置と、選択されなかったポリゴンに対して座標計算
   を行う第２の画素座標計算装置と、前記第１、第２の画
   素座標計算装置から得られた画素座標の画素について画
   素データを演算する画素データ演算器と、前記画素デー
   タ演算器の演算結果を格納するフレームメモリとを備え
   た画像生成装置。