JPH04220781A - 画像を表す複数の多角形を処理する装置及び方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【発明の分野】本発明は、図形変形エンジンに関するも
のであり、更に詳細には、画像を表わす入力多角形を台
形に分解するプロセスおよび装置であって、ラスタ走査
変換システムにより一層効率良く行うことができるもの
に関する。

【０００２】

【従来技術の説明】従来技術のラスタ図形システムは一
般に明確な二つの部分を備えている。光景の幾何学的説
明をユーザの観点に従って変形し、明らかにする図形変
形エンジン、および変形した光景を表示画面に画く描写
器、である。周知のように、光景の幾何学的説明は任意
の数の辺を有する複数の多角形の組合せから成ることが
ある。換言すれば、表示すべき三次元画像が明暗の異な
る多角形から成る表面として記述されている。ここに使
用するように「多角形」とは頂点Ｖ〔１〕・・・・Ｖ〔
Ｎ〕の順序良く整列した集合体を言う。ただしＮは多角
形の頂点の数である。これら頂点は、多角形のＮ個の辺
を規定するが、これらの辺は端点がそれぞれの頂点Ｖ〔
１〕・・・・Ｖ〔Ｎ〕で作られる線分Ｅ〔１〕・・・・
Ｅ〔Ｎ〕である。たとえば、線分Ｅ〔１〕は端点Ｖ〔１
〕およびＶ〔２〕を所持することができるが、線分Ｅ〔
２〕は端点Ｖ〔２〕及びＶ〔３〕を所持することができ
る。このような多角形は図形変形エンジンにより、各多
角形の頂点の座標（Ｘ、Ｙ、Ｚ）のような情報の他に各
頂点に対する明暗情報および画素レベルの描写計算すべ
てについて図形変形エンジンで処理される指令を含む一
連の図形プリミティブとして識別される。

【０００３】光景をこのように幾何学的に表現すること
により、画素画像データを表示画面にするのに必要な図
形変形エンジンによる処理が大幅に容易になる。図形変
形エンジンは一般に、図形文脈の管理、マトリックス変
形の計算、スプライン市松模様照明モデル（ｓｐｌｉｎ
ｅ　ｔｅｓｓｅｌｌａｔｉｏｎ　ａｎｄｌｉｇｈｔｉｎ
ｇ　ｍｏｄｅｌ）の計算を含むこのようなデータに関す
る多数の任務を実行する。変形エンジンはベクトルおよ
び多角形描写ハードウェアを制御することもできる。し
かし、このような計算は一般に極めて複雑且つ時間のか
かるものであり、非常に多くの処理能力を必要とし、そ
の結果処理の困難さが従来のラスタ図形システムにより
画像を描写できる速さの主な制約になることが屡々であ
った。

【０００４】

【発明が解決しようとする課題】上述の問題点を解決す
る最も普通の提案は図形変形エンジンの処理能力を増す
ことであった。たとえば、複数の変形エンジンを並列に
設けてそれぞれの各多角形の処理を並列に行うことがで
きるようにする。しかし、このようなシステムは極めて
複雑で且つ経費がかかり、やはり多角形を効率良く処理
しない。その結果、図形原線情報はこれまで甚だ制限さ
れてきた。したがって、図形変形エンジンの処理効率を
向上させて多数の簡単な多角形から成る複雑な三次元画
像をも対話式の速さで描写することができるようにする
手段を設けることが望ましい。

【０００５】したがって、当業界では、伝統的な図形変
形エンジンの性能を、入力多角形を真に対話式の速さで
処理することができるように高めるプロセスおよび装置
の必要性が長い間感じられている。当業界ではまた三角
形および四辺形のような簡単な多角形の描写を加速して
図形パイプラインについて一層高速且つ容易な走査変換
を達成するようにすることができるシステムの必要性が
長い間感じられている。本発明はこれら必要性を満たす
ように計画されたものである。

【０００６】

【課題を解決するための手段】当業界での上述の長い間
感じられていた必要性は、図形変形エンジンの多角形処
理作業の多くを処理効率を向上するように処理する手段
を設けることによる本発明により満たされる。特に、三
角形および四辺形のような簡単な入力多角形を走査変換
システムで高速で容易に描写することができる台形に分
解するプロセスおよび装置が提供されている。ほとんど
の多角形データベースは三角形および四辺形を主として
含んでいるので、本発明の台形化回路は通常、大部分の
多角形を図形システムで分解し、これにより全体の処理
性能を５０％も増すことができる。

【０００７】本発明によれば、表示装置に表示すべき画
像を表わす、各々が画像の再生中表示装置により描写さ
れる所定数以下の辺を有する複数の多角形、を処理する
装置が提供される。本発明によるこのような装置は好適
には、表示すべき画像の各入力多角形について辺データ
を提供する手段、および所定数以下の辺を有する各入力
多角形を、各々がその中の正確に二つの辺が表示装置の
一つの座標方向に平行でない３辺または４辺を有する閉
じた四辺形である少なくとも一つの台形に分解する台形
化手段から構成されている。各入力多角形の各台形に対
する辺データは表示装置に出力されて描写を容易にする
。好適には、辺データ提供手段は所定数を超える辺を有
するそれら入力多角形を処理してすべての入力多角形を
処理することができるようにする手段を備えている。

【０００８】本発明の好適実施例では、台形化手段は、
各入力多角形についての辺データを格納するＲＡＭ、各
入力多角形の各辺の端点を決定する手段、および端点を
各端点の座標値に従って座標方向に垂直な方向に順序良
く整列させる手段、から構成されている。このような実
施例の台形化手段は、各入力多角形の辺の順序良く整列
された端点を格納し、各端点が座標方向に垂直な方向の
どの端点を表わしているかを示すフラグを格納するスタ
ックレジスタをも備えることができる。

【０００９】本発の他の好適実施例では、処理手段は各
入力多角形のそれぞれの各辺の各端点の座標方向に垂直
な方向の座標値を決定し、各辺についてのこれらの値を
スタックレジスタに格納することができる。

【００１０】本発明の装置はこのようにして入力多角形
の各台形を形成する。その台形は、入力多角形の辺の開
始端点から座標方向に垂直な方向に、座標方向に垂直な
方向で入力多角形の辺の最初に出会う端点にまで展開し
ている。その場合に、開始端点のフラグは、開始端点が
辺の座標方向に垂直な方向に対して最少座標値を備えて
いることを示しており、さらに、また、最初に出会う端
点のフラグは、最初に出会う端点が座標方向に垂直な方
向で入力多角形の辺の最大座標値を備えていることを示
している。したがって出力台形の辺は座標方向に平行な
方向に、入力多角形の第１の辺から第２の辺まで延びて
おり、座標方向に平行な辺は開始端点および最初に出会
う端点を通過する。好適には、開始端点および最初に出
会う端点は順序良く整列されたスタックレジスタから座
標方向に垂直な方向に異なる座標値を有するそれぞれの
エントリとして取出される。

【００１１】本発明は、表示装置に表示すべき画像を表
わす、各々が所定数以下の辺を有する複数の多角形を関
連辺データと共に処理する方法をも備えている。本発明
によるこのような方法は好適には下記諸段階から構成さ
れている。

【００１２】表示すべき画像の各入力多角形に対する辺
データを提供する段階、所定数以下の辺を有する各入力
多角形を少なくとも一つの台形であって、その内の２つ
以下の辺が表示装置の座標方向に平行でない、３辺また
は４辺を備えた閉じた四辺形である台形に分解する段階
、各入力多角形の各台形に対する辺データを表示装置に
出力する段階。

【００１３】好適実施例によれば、多角形分解段階は、
各入力多角形に対する辺データを格納する段階、各入力
多角形の各辺の端点を決定する段階、および端点を各端
点の座標値に従って座標方向に垂直な方向に順序良く整
列させる段階、から構成される。多角形分解段階は、各
入力多角形の辺の順序良く整列された端点を格納する段
階、および各端点が座標方向に垂直な方向にどの端点を
表わしているかを示すフラグを格納する段階を備えるこ
ともできる。他に、多角形分解段階は、各入力多角形の
それぞれの各辺の各端点の座標方向に垂直な方向の座標
値を決定する段階、および各辺に対するこれらの値を格
納する段階を備えることもできる。

【００１４】本発明の好適な方法はまた、描写した多角
形が座標方向に垂直な方向に、開始端点のフラグが開始
端点が辺に対する座標方向に垂直な方向に最小座標値を
有していることを示している、入力多角形の辺の開始端
点から、最初に出会う端点のフラグが最初に出会う端点
が座標方向に垂直な方向に入力多角形の辺に対する最大
座標値を有していることを示している、座標方向に垂直
な方向に入力多角形の辺の端点が最初に出会う端点まで
拡がっており、座標方向に平行な方向に、入力多角形の
第１の辺から第２の辺まで拡がっており、座標方向に平
行なこれらの辺は開始端点および第１に出会端点を通過
する。このうよな描写は、開始端点、座標方向に垂直な
方向の、開始端点を最初に出会う端点との間の座標値の
差を指定するデータ、および入力多角形の第１および第
２の辺を指定する辺データと共に台形描画指令を使用し
て行うことができる。

【００１５】本発明の他の好適実施例によれば、表示装
置に表示すべき画像を表わす、各々が所定数以下の辺を
有する複数の多角形を関連辺データを用いて処理する方
法であって、所定数以下の辺を有する各入力多角形のそ
れぞれの頂点を読込む段階、各入力多角形の各辺の走査
方向に垂直な座標方向の最大および最小の座標値を決定
する段階、各入力多角形を、各々がその中で表示装置の
座標方向に平行でない辺が二つより多くない３辺または
四辺を有する閉じた四辺形である、少なくとも一つの台
形に分解する段階、および各入力多角形の各台形の辺デ
ータを表示装置に出力する段階、から成る方法が提供さ
れる。

【００１６】好適には、このような方法の多角形分解段
階は、頂点を区分して頂点の座標値を座標方向に整列さ
せる段階、区分した各頂点について、入力多角形のその
関連する辺に対する走査方向に垂直な座標方向にその頂
点が最大座標値を有しているか最小座標値を有している
かを決定する段階、最大座標値を有する頂点に出会うま
で入力多角形の区分した頂点のそれぞれの辺に対する辺
データを読み込む段階、入力辺に対する最小座標値を有
する頂点からその関連する辺の方向に対して最大座標値
を有する頂点まで走査方向に垂直な方向に拡がっている
台形を作る段階、および入力多角形の新しい辺を読込ん
で辺を最大座標値を有する頂点を置き換える段階、とを
含んでいる。

【００１７】入力多角形の新しい辺は好適には入力多角
形のすべての点が読込まれて対応する台形が作られるま
で読み込む。

【００１８】したがって本発明によるプロセスおよび装
置は、走査変換システムに与えられる台形が従来技術の
図形表示装置の走査変換システムにより屡々受取られる
典型的な多辺多角形よりはるかに容易に描写することが
できるのでかなり処理を高めることができる。本発明の
下記詳細説明から更に他の利益が明らかになろう。

【００１９】

【実施例】ここに開示され、特許請求している主題事項
の発明者は当業間の長い間感ぜられていた上述の必要性
を、小さな入力多角形を走査変換装置により容易に描写
することができる台形に分解する台形化回路を開発する
ことにより満たした。次の説明から明らかであるように
、本発明の台形化回路（今後「トラッパ」と呼ぶ）は、
システム全体の性能を上げるために入力多角形を処理す
る図形変形エンジンのサブシステムとして動作する。特
に、小さな入力多角形を台形に分解することにより、こ
のサブシステム（今後「多角形プロセッサ」と呼ぶ）は
図形変形エンジンを簡単な多角形を分解しなければなら
ないことから解放する。その上、多角形データベースの
ほとんどは、三角形および四辺形のような主として簡単
な多角形を備えてるので、トラッパは一般に図形変形エ
ンジンで処理されたほとんどの多角形を分解し、これに
よりかなりな性能の向上が少い費用で行われる。

【００２０】本発明の現在のところ好適な模範的実施例
によるこれらおよび他の有利な特徴を有するプロセスお
よび装置について今度は図１〜図６を参照して説明する
ことにする。当業者にはここに示す説明が例示目的だけ
のためのもので、どのようにしても本発明の範囲を限定
しようとするものではないことを認めるであろう。本発
明の範囲に関するあらゆる疑問は付記した特許請求の範
囲を参照することにより氷解することができる。

【００２１】図１はホストインタフェース１０４を経由
して図形サブシステムと接続されているホスト処理シス
テム１０２を示す。図示のように、図形サブシステムは
一般にその出力が図形描写回路１０８に供給される図形
変形エンジン１０６を備えている。図形描写回路１０８
の出力はフレームバッファ１１０に加えられ、その出力
はラスタ表示装置１１２により受取られ、たとえばＣＲ
Ｔ画面に出力される。以下に詳細に説明するように、本
発明は特に、変形エンジン１０６および入力画像を表わ
す一定の多角形の台形に細分して一層効率良く画像描写
を行うことができる手法を目指している。

【００２２】本発明による変形エンジン１０６を図２に
更に詳細に示す。図示のように、変形エンジンは典型的
には描写すべき画像を表わす入力多角形を入力先入れ先
出しバッファ（入力ＦＩＦＯ）２０２を経由して受取る
。受取られた多角形は次に、変形プロセッサとして使用
されるようプログラムされる汎用プロセッサとすること
ができる変性プロセッサ２０４により入力ＦＩＦＯ２０
２から順次読取られる。変形プロセッサ２０４の出力は
次に多角形プロセッサ２０８に入力される前に他のＦＩ
ＦＯに入力されるが、この多角形プロセッサ２０８も当
業者には明らかなように特別にプログラムされる汎用プ
ロセッサでもよい。多角形プロセッサ２０８は典型的に
は辺斜面計算およびサブ画素調節におよび指令を下流ハ
ードウェアに供給することに責任がある。しかし、本発
明によれば、多角形プロセッサ２０８により行われる処
理は、所定数以下の辺を有する簡単な入力多角形を表示
画面の座標方向に平行な一つまたは二つの辺を有する台
形に分解する台形化回路（トラッパ）２１０を追加する
ことによりかなり簡単になる。以下に更に詳細に説明す
るように、トラッパ２１０は四つ以下の辺を有する簡単
な多角形を台形に細分するが、当業者は本発明の手法を
処理の簡易性および速度をそれ以上失うことなく更に複
雑な多角形に使用することができることを認めるであろ
う。所定数より多い辺を有する多角形は変形プロセッサ
２０４および／または多角形プロセッサ２０８でやはり
処理される。得られる台形を次に描写のために出力ＦＩ
ＦＯ２１２を経由して下流ハードウェアに送る。

【００２３】トラッパ２１０は、多角形プロセッサ２０
８のハードウェアの費用を減らすように且つトラッパ２
１０と多角形プロセッサ２０８とを結合するのに余分な
ハードウェアを必要としないように多角形プロセッサ２
０８のハードウェアの一部であるＣＭＯＳゲートアレイ
として設計することができる。トラッパ２１０はここで
「台形化」と言うプロセスを通して受取る辺データから
台形を作る。ここで使用するように、「台形化」とは入
力多角形を表示装置の座標軸に平行な１辺または２辺を
有する一つ以上の台形領域に細分するプロセスを意味す
る（台形の上辺または下辺のいずれかが退化していると
き、すなわち、三角形の場合のように、一点であるとき
、１辺だけが座標軸に平行である）。その他に、ここで
記す実施例の場合、トラッパ２１０は二つ、三つ、また
は四つの頂点を有する入力多角形およびＹで凸になって
いる入力多角形についてのみ台形化を行う。Ｙの凸性は
多角形の性質であり、これにより多角形はどんな走査線
においても２を超える辺数を有することは決してなく、
互いに交差する非水平辺を有する台形の処理を必ずしも
妨げない。これら要求事項を満たしていないどんな入力
多角形もトラッパ２１０によって処理されることはなく
、代りに多角形プロセッサ２０８および／または変性プ
ロセッサ２０４により完全に処理され、結果はトラッパ
２２０を通して真直ぐ出力に簡単に伝えられる。これら
要求事項の重要性はトラッパ２１０の以下の詳細な説明
から一層明らかになるであろう。

【００２４】図３はトラッパ２１０の現在のところ好適
な実施例のブロック図を概略的に示している。図３に示
すように、多角形プロセッサ２０８の出力は、台形を作
っている最中でも、またはその出力ポートが丁度押さえ
られているときでも辺データをトラッパに書き込むこと
ができるようにするＦＩＦＯ３０２に入力される。この
目的でＦＩＦＯ３０２を非常に深くする必要はなく、典
型的には３２語の深さであり、これは四辺形の極端な場
合をあふれ無しに取扱うのに丁度充分である。ＦＩＦＯ
３０２から書込まれた辺データは次に辺ＲＡＭ３０４に
格納される。ただし、多角形が二つ、三つ、または四つ
の頂点を有しないかまたはＹ凸でない上述の場合には、
ＦＩＦＯ３０２からの辺データを直接トラッパ２１０を
通して出力に伝えることができる。

【００２５】図５および図６を参照して以下に詳細に説
明するアルゴリズムによれば、トラッパ２１０は多角形
プロセッサ２０８および制御器３０６により制御されて
、入力多角形の辺の斜面の他にそれぞれの辺の端点をも
決定することにより、辺ＲＡＭ３０４に格納されている
入力多角形の辺を処理する。やはり以下に説明するよう
に、辺の端点のＹ座標値（走査線に垂直な方向の）はＹ
区分器３０８により区分けされるが、この区分器の実施
例は、本出願と同じ譲受入れに譲渡され、ここに引用に
より組入れてある、１９９０年２月９日出願の米国特許
出願第４７８１２６号に見ることができる。得られる台
形の区分されたＹデータは更に処理するためＹスタック
３１０に格納される。たとえば、出力台形の特定の辺を
画くＹの開始値はＹスタック３１０に格納され、これに
よりＹの開始値およびＹの終点値の台形の走査線の数を
決定するのに使用することができる。トラッパ２１０に
より出力されたどの語が下流ハードウェアにより指令と
して解釈されるかを決定する指令タグビット、および下
流ハードウェアにタグ付き語が目的を実行するための論
理ブロックの一部として考えるべき最後のものであるこ
とを示す終了タグビットを発生する指令語レジスタ３１
２を設けることもできる。したがって、トラッパが台形
に画くよう指令されると、指令タグビットが設定され、
一方終了タグビットはクリアされる。指令に続く他のす
べてのデータは両ビットをクリアさせる。タグビットの
他に辺ＲＡＭ３０４からの辺データおよびＹスタック３
１０からのＹ開始値および走査線値は組合せてマルチプ
レクサ３１４により指令／データパケットとして下流ハ
ードウェアに出力することができる。

【００２６】トラッパ２１０は多角形に関する必要なす
べてのデータを多角形を台形に分解する前に受取らなけ
ればならない。このデータにはＹ区分器３０８に格納さ
れている各辺についての最小および最大のＹ値の他に辺
ＲＡＭ３０４に格納されている各辺に関する属性がある
。このデータを受取ると、台形発生指令が多角形プロセ
ッサ２０８によりトラッパ２１０に書込まれ、すべての
データが存在することおよび台形の作成を進めることが
できることをトラッパに知らせる。以下に説明するよう
に、トラッパ２１０は入力多角形の各辺に対する最小の
Ｙ値および最大のＹ値を区分し、これらを順次比較して
台形の終りが何時見つかったかを判定する。トラッパ２
１０はこのように動作し、台形データを出力し、トラッ
パ２１０が台形を作るのに忙しい間はその入力ＦＩＦＯ
３０２に前に説明したように次の多角形に対するデータ
と共に書込むことができる。トラッパが作業するのに適
していない多角形は多角形プロセッサ２０８および／ま
たは変形プロセッサ２０４により分解され、得られるデ
ータは単にトラッパ２１０を通してマルチプレクサ３１
４により指令／データ出力パケットに組合わされるため
に伝えられるだけである。

【００２７】多角形プロセッサ２０８により実施されて
必要な入力データを供給すると共にトラッパ２１０によ
り実施されて台形を作るアルゴリズムの詳細を今度は図
４〜図６を参照して説明することにする。

【００２８】図４は頂点Ａ（Ｘａ、Ｙａ、Ｚａ）、Ｂ（
Ｘｂ、Ｙｂ、Ｚｂ）、Ｃ（Ｘｃ、Ｙｃ、Ｚｃ）、および
Ｄ（Ｘｄ、Ｙｄ、Ｚｄ）により規定される試料入力多角
形の実施を示す。図４に示すように、トラッパ２１０は
頂点Ａ、Ｂ、ＣおよびＤにより規定される多角形を頂点
Ａ、Ｂ、およびＥを有する三角形、頂点Ｂ、Ｅ、Ｃ、お
よびＦを有する台形、および頂点Ｃ、Ｄ、およびＦを有
する他の三角形にそれぞれ細分する。トラッパ２１０が
図４のこの台形化を行う手法について今度は図５および
図６の流れ図を参照して説明することにする。

【００２９】上に注記したように、特定の入力多角形を
記述する辺データは多角形プロセッサ２０８からＦＩＦ
Ｏ３０２に出力され、そのデータは辺ＲＡＭ３０４に格
納される。図５および図６に使用するように、多角形プ
ロセッサ２０８により受取られる頂点データは変数「頂
点カウント」により規定されるそれぞれの頂点（数にし
て三つか四つ）のアレイから構成されていると仮定する
。頂点のアレイを図５および図６では頂点〔Ｉ〕と称し
ている。 ただしＩはアレイのＮ番目の要素へのアクセスを頂点〔
Ｎ〕と示すようにアレイを指す指標であり、アレイの最
初の要素は指標Ｉ＝１を備えているがこれは頂点アレイ
から頂点を読出すごとに増加する。その他に、頂点アレ
イ内の各頂点はそのＸ、Ｙ、およびＺ座標により識別さ
れ、頂点アレイ内の第２の頂点のＸ座標フィールドへの
アクセスは頂点〔２〕．Ｘのような例により示される。 また、図５のアルゴリズムでは、一対の変数が頂点１お
よび頂点２として規定される。これら各頂点変数は頂点
アレイ内の頂点セルの値を取ることができ、頂点１．Ｘ
または頂点１．Ｙのように頂点フィールドにアクセスす
るのに使用することができる。

【００３０】入力多角形の辺の端点を多角形プロセッサ
２０８により決定する動作を今度は図５について説明す
ることにする。説明は図４に示す多角形の台形化の場合
に向けることにするが、当業者はこのプロセスを上に示
した判定基準を満たす他のどんな入力多角形にも容易に
適用することができることを認めるであろう。

【００３１】最初に、入力多角形の頂点のアレイをＦＩ
ＦＯ２０６から多角形プロセッサ２０８に読込む。たと
えば、図４に示す多角形の場合については、頂点をシー
ケンスＡ、Ｂ、Ｄ、およびＣに読込むことができ、これ
により隣接頂点が多角形の同じ辺の端点を規定する。多
角形プロセッサ２０８は次に段階５００で始動し、段階
５０２で頂点アレイ指標Ｉを１に等しく設定して頂点ア
レイの第１のエントリ（頂点Ａ）にアクセスする。次に
Ｉが段階５０４で頂点カウント（４）と比較される。Ｉ
が頂点カウントより大きければ、すべての頂点が読込ま
れ、多角形が段階５０６で以下に図６で記したように台
形に細分される。こうして処理は段階５０８で終る。し
かし、Ｉが頂点カウントにより大きくなければ、変数頂
点１は段階５１０で頂点アレイの最初の要素の値に設定
されるが、これは示した例では頂点Ａである。段階５１
２で指標は頂点カウントと等しくないから、変数頂点２
は段階５１４で頂点アレイの第２の要素、すなわち、頂
点Ｂ、の値に割当てられる。他方、Ｉが段階５１２で頂
点カウントに等しければ、頂点アレイの第１の頂点（頂
点Ａ）が段階５１６で頂点２に割当てられる。多角形プ
ロセッサ２０８は次に段階５１８で変数頂点１（頂点Ａ
）に割当てられた頂点のＹ値が変数頂点２（頂点Ｂ）に
割当てられた頂点のＹ値より大きいかチェックされる。 頂点ＡのＹ値が頂点ＢのＹ値より大きければ、変数頂点
１および頂点２の値が段階５２０で交換される。しかし
、図４の多角形に対しては頂点ＢのＹ値が頂点ＡのＹ値
より大きいから、処理は直接、変数ｙｔｏｐおよびｙｂ
ｏｔを計算する段階５２２に進む。

【００３２】ｙｔｏｐは入力多角形の辺について画くべ
き最初の画素の整数Ｙ値であるが、ｙｂｏｔは辺につい
て画くべき最後の画素の整数Ｙ値より１大きい整数Ｙ値
に対応するもので、これにより辺を画くとき「ｏｆｆ　
ｂｙ　ｏｎｅ」誤差が除去される。図４の例の場合には
、頂点１は頂点Ａを表わし、頂点２は頂点Ｂを表わして
いるから、ｙｔｏｐは実質上Ｙａに対応し、ｙｂｏｔは
実質上Ｙｂに対応する。 図４に示すように、これらは辺ＡＢの端点である。同様
に、変数ｘｔｏｐは辺について画くべき最初の画素のＸ
値に対応し、一方変数ｚｔｏｐは辺について画くべき最
初の画素のＺ値に対応する。したがって、画くべき最初
の画素は座標（ｘｔｏｐ、ｙｔｏｐ、ｚｔｏｐ）を有し
ており、ここでｙｔｏｐは整数であり、他の値は必らず
しも整数ではない。

【００３３】段階５２２でｙｂｏｔおよびｙｔｏｐを求
めてから、多角形プロセッサ２０８は段階５２４でｙｂ
ｏｔがｙｔｏｐ以下であるかチェックし、もしそうであ
れば、処理は段階５２６に進み、Ｉを増してループを繰
返す。しかし、ｙｂｏｔのＹ値がｙｔｏｐのＹ値より大
きければ、多角形プロセッサ２０８は段階５２８に進み
、ｘｔｏｐおよびｘｓｌｏｐｅの値を辺ＲＡＭ３０４に
格納されているデータを使用して次のように計算する。

【００３４】

【数１】

【００３５】同様に、段階５３０でｚｔｏｐおよびｚｓ
ｌｏｐｅを辺ＲＡＭ３０４にあるデータを使用して次の
ように計算する。

【００３６】

【数２】

【００３７】次に、段階５３２でこれら変数の値を辺Ｒ
ＡＭ３０４に書込む。段階５３４でｙｔｏｐの値をＹス
タック３１０に書込み、ＭＩＮフラグを設定してこの値
がｙｔｏｐであることを示し、同様に、段階５３６でｙ
ｂｏｔの値をＹスタック３１０に書込み、ＭＡＸフラグ
を設定してこの値がｙｂｏｔであることを示す。換言す
れば、ｙｔｏｐの値は辺ＡＢの上端として識別されるが
、ｙｂｏｔの値は辺ＡＢの下端として識別される。処理
は次に段階５２６に進み、Ｉ値を増してループを繰返す
。

【００３８】処理はこの仕方ですべての頂点が頂点アレ
イから読込まれてしまうまで進行する。処理は次に段階
５０４ですべての頂点が読込まれてしまったことを判断
し、多角形プロセッサ２０８が図６に関して後に説明す
るように入力多角形を台形に分解するよう指令する。こ
のようにして、それぞれＡ、Ｂ、Ｄ、およびＣの入力頂
点アレイを有する図４の多角形の場合、Ｙスタック３１
０には処理が段階５０６に進んだとき下記のものが入っ
ていることになる。

【００３９】Ｙ値　　　　フラグ　　　　辺Ｙａ　　　
　ＭＩＮ　　　　ＡＢ Ｙｂ　　　　ＭＡＸ　　　　ＡＢ Ｙｂ　　　　ＭＩＮ　　　　ＢＤ Ｙｄ　　　　ＭＡＸ　　　　ＢＤ Ｙｃ　　　　ＭＩＮ　　　　ＣＤ Ｙｄ　　　　ＭＡＸ　　　　ＣＤ Ｙａ　　　　ＭＩＮ　　　　ＡＣ Ｙｃ　　　　ＭＡＸ　　　　ＡＣ Ｙスタック３１０が今述べた図５のアルゴリズムに従っ
て作られてしまうと、入力多角形は、今度説明するよう
に、図６に示すアルゴリズムに従って台形に細分される
。

【００４０】上に注記したとおり、Ｙスタック３１０に
は入力多角形の各辺に対する最大および最小のＹ値につ
いての情報を持つ語のアレイが入っている。この目的で
、Ｙスタック３１０の各語は好適に、整数Ｙ値を識別す
るフィールド、格納されている値が辺に対するＭＩＮ　
　Ｙ値であるかＭＡＸ　　Ｙ値であるかを指定するＭＩ
ＮまたはＭＡＸフラグ、およびＹスタック３１０のその
エントタリに関連する辺を表わす辺フィールド、を備え
ている。この仕方で、各値がその対応する辺と共に識別
される。Ｙスタック３１０の中にある各語にはここでは
ｙｓｔａｃｋポインタを介してアクセスすることができ
る。ｙｓｔａｃｋポインタは、Ｙ整数値、ＭＩＮまたは
ＭＡＸフラグ、または辺フィールドを表わすＹスタック
３１０の各語のフィールドを指す。

【００４１】図６に示すように、トラッパ２１０は段階
６００で上述のＹスタック値を用いて始動し、辺ポイン
タレジスタ辺Ａおよび辺Ｂを段階６０２で「空」に設定
し、辺ポインタがどの辺をも指していないこと示す。当
業者には明らかであるように、これら辺ポインタは代り
にそれを格納されている、レジスタがポインタを備えて
いないことを示す値を所持することができる。辺ポイン
タは、現在の台形を規定する辺の辺ＲＡＭ３０４の中の
トラックを保持するのに使用され、以下に説明するよう
に、Ｙスタック３１０を横断するにつれて入力多角形の
辺の一つを表わす値がロードされ、アンロードされる。 また、新辺Ａおよび新辺Ｂと呼ばれる二つの「新しい辺
」フラグを使用して真および偽の値を取り、辺ポインタ
レジスタに入っている辺が新しい辺であるが現存する辺
であるかを示すことができる。これらフラグは、幾つか
の辺は共有され、したがって、台形を出力するとき二度
読取る必要がないという事実を活用するのに使用される
。このことは以下の説明から明らかになろう。

【００４２】辺Ａおよび辺Ｂの値が段階６０２で空に設
定されてから、図５に関して説明した処理の期間中Ｙス
タック３１０に格納されている値は段階６０４で区分さ
れる。上に述べたように、このプロセスは、Ｙ区分器３
０８により行われるが、この区分器は前記関連出願に記
述されている形式の高速区分装置を備えることができる
。特に、Ｙスタック３１０はＹの最小値からＹの最大値
までスタック３１０にある語の数値フィールドの上昇順
に区分される。二つ以上のエントリが同じ数値フィール
ドを備えていれば、ＭＡＸに等しいフラグを有するエン
トリがＭＩＮに設定されたフラグを有するエントリの前
に到来する。それはデータは次の辺の始めの前に一つの
辺の終りを示すことが必要だからである。

【００４３】たとえば、図４に示す多角形の隣接する二
つの辺ＡＢおよびＢＤについて、Ｙｄ＞Ｙｂ＞Ｙａであ
る。各辺はＹスタック内で二つのエントリを所持してお
り、一つはＭＩＮフラグを一つはＭＡＸフラグを有して
いる。その他、辺ＡＢの　　ＭＡＸエントリは辺ＢＤに
対するＭＩＮエントリの数値フィールドに等しい数値フ
ィールドを備えていなければならない。その上、ＭＩＮ
エントリがその数値フィールドにＭＡＸエントリに対す
る数値フィールド内の値以上の値を備えているように一
つの辺に対して１対のエントリが決して存在してはなら
ない。したがって、図４に示す入力多角形のＹスタック
３１０が段階６０４でＹ区分器３０８により区分される
と、Ｙスタック３１０は下記のものをこの順序に備えて
いる。

【００４４】Ｙ値　　　　フラグ　　　　辺Ｙａ　　　
　ＭＩＮ　　　　ＡＢ Ｙａ　　　　ＭＩＮ　　　　ＡＣ Ｙｂ　　　　ＭＡＸ　　　　ＡＢ Ｙｂ　　　　ＭＩＮ　　　　ＢＤ Ｙｃ　　　　ＭＡＸ　　　　ＡＣ Ｙｃ　　　　ＭＩＮ　　　　ＣＤ Ｙｄ　　　　ＭＡＸ　　　　ＢＤ Ｙｄ　　　　ＭＡＸ　　　　ＣＤ Ｙスタック３１０が段階６０４で区分されると、Ｙスタ
ックポインタが段階６０６で最初のＹスタックエントリ
に割当てられ、Ｙスタックポインタの数値フィールド内
のエントリが段階６０８で最初の出力台形に対するＹ開
始値として割当てられる。トラッパ２１０は次に段階６
１０でＭＩＮフラグがＹスタックポインタにより指され
ている語に対して設定されているかチェックし、これが
上に示した区分されたＹスタック３１０の最初のエント
リに対する場合であるから、処理は段階６１２に進み、
辺レジスタ辺Ａが空であるか否か判定する。これは図６
の流れ図を通過する最初の場合であるから、段階６１８
でＹスタックの最初のエントリの辺フィールドにある辺
ＡＢが辺レジスタ辺Ａに読込まれ、新辺Ａが真に設定さ
れ、処理が段階６３２に進む、しかし、辺レジスタ辺Ａ
が、ループの次の繰返しの期間中のように、区分された
辺数値を既に所持していれば、処理は段階６１２から段
階６１４に進み、辺レジスタ辺Ｂが空であるか否か判定
される。どの辺レジスタも空でなければ、段階６１６で
エラー信号が発生する。辺レジスタ辺Ｂが空であれば、
段階６２０で入力辺の値が辺レジスタ辺Ｂで区分され、
新辺Ｂが真に設定され、処理が段階６３２に進む。

【００４５】トラッパは段階６３２でＹスタックポイン
タがスタック３１０の最後のエントリにあるかチェック
し、もしそうであれば、処理は段階６３４で終了する。 そうでない場合には、Ｙスタックポインタが段階６３６
で次のＹスタックエントリまで進む。トラッパは次の段
階６３８で、段階６０８で設定されたＹ開始の値が進ん
だＹスタックポインタ値により指されている数値フィー
ルド内の値に等しいかチェックする。与えられた試料に
対して二つ共Ｙａに等しいから、処理は段階６０８に逆
に進み、辺ＡＣを段階６２０で辺レジスタ辺Ｂに読込む
。

【００４６】しかし、段階６３８で、Ｙ開始値が現在進
んだＹスタックポインタ値に対応しないと判定されれば
、トラッパ２１０は他の辺を読込む必要はなく、処理は
段階６４０に進み、ここでトラッパ２１０は辺レジスタ
辺Ａかまたは辺レジスタ辺Ｂかが空であるかチェックす
る。辺レジスタの一方または両方が空であれば、段階６
４２でエラー信号が指示される。二つの辺がそれぞれの
辺レジスタに存在すると、段階６４４で図４に示す領域
ＡＢＥに対してＹ開始値Ｙａを使用して台形描画指令が
発生する。新辺Ａ及び新辺Ｂのフラグが段階６４６で偽
に設定されてから処理は段階６０８に戻って次の台形に
台する次のＹ開始値を読込む。

【００４７】ループの次の繰返しの期間中、最後のｙｓ
ｔａｃｋポインタフラグがＭＡＸフラグであったから、
段階６１０で処理は段階６２２に進み、Ｙスタックポイ
ンタの辺フィルードに辺レジスタ辺Ａに格納されている
ものと同じ辺が入っているか判定する。辺レジスタ辺Ａ
及びＹスタック３１０の第３のエントリには共に辺ＡＢ
が入っているから、辺レジスタ辺Ａは段階６２８で空に
設定される。換言すれば、図４の多角形に対して頂点Ｂ
には頂点Ｃより先に到達しているから、辺レジスタ辺Ａ
は空に設定され、次の辺を辺レジスタ辺Ａに読込むこと
ができるようになる。同様に、段階６２４で次の辺が辺
レジスタ辺Ｂの中にあるものと同じであると判定されれ
ば、辺レジスタ辺Ｂ段階６３０で空に設定される。しか
し、次の辺がいずれの辺レジスタに入っているものとも
対応しなけば、段階６２６でエラー信号が発生する。

【００４８】読込むべき次の辺は辺ＢＤであり、辺ＢＤ
はＹｂに最小Ｙ値が、Ｙｄに最大Ｙ値がある。辺ＢＤは
空の辺レジスタ（辺Ａ）に格納されている。処理はこの
仕方でトラッパ２１０が段階６３２でＹスタック３１０
のすべてのエントリが処理されてしまい、処理を段階６
３４で終了することができると判定するまで進行する。

【００４９】上に注記したように、台形描画指令が段階
６４４で発生し、辺レジスタ辺Ａおよび辺Ｂにある辺数
値、Ｙ開始値、および台形の端までの走査線の数と共に
出力される。特に、台形描画指令は台形が従う指令、お
よびこの指令に続いて開始台形Ｙ値、開始台形Ｙ値から
出発する台形の走査線の数、開始Ｘ値、Ｙの各段階に対
するＸの変化の割合、開始Ｚ値、およびＹの各段階に対
するＺの変化の割合を含むデータを出力することにより
形成することができる。このデータは次に適切な値を辺
ＲＡＭ３０４またはＹスタック３１０のいずれか該当す
るものから読出すことにより台形の他の辺に対して出力
される。次に台形描画指令は下流の描写回路に送られ、
入力画像の各多角形を適切に描写できるようにする。

【００５０】トラッパ２１０により発生される台形描画
指令は、適切な台形頂点に対応するデータを備えている
あらかじめ指定した頂点の数を示す幾つかのフィールド
を備えることができる。したがって、頂点フィールドは
、二つ以上が同じ頂点に対応するに違いないので、四つ
の異なる頂点を指す必要はない。この一例は台形の上辺
の長さが０、すなわち、図４に示す三角形ＡＢＥの場合
のように、三角形を描写すべきときに発生する。他に、
入力多角形の二つの連続して描写される台形が屡々一辺
を共有しているから、台形を表示するとき共通辺に対す
る斜面情報を伝達する必要はない。代りに、伝達された
データ内のビットは台形が一つ以上の先の台形と一辺を
共有することを示すべきである。たとえば、フラグ新辺
Ａおよび新辺Ｂをこの目的に使用することができる。

【００５１】

【発明の効果】ここに説明するような本発明の台形化ユ
ニットは、入力多角形をはるかに効率良く処理すること
ができるという点で従来の変形エンジンにより性能がか
なり向上している。システム全体の性能は本発明の分解
技法により５０％も向上することができる。それは走査
変換システムを、完全な多角形について動作しなければ
ならないものよりはるかに高速に且つ簡単にすることが
できるからである。その他に、この性能の向上は比効的
低い費用で達成される。その上、多角形データベースの
ほとんどは主として三角形および四辺形を備えているの
で、本発明は通常、システムによりほとんどの多角形を
分解する。

【００５２】本発明の一つの模範的実施例について上に
詳細に説明してきたが、当業者は、本発明の新規な教示
および長所から実質的に逸脱することなく模範的実施例
に多数の他の修正を加えることが可能であることを容易
に認めるであろう。たとえば、入力多角形の頂点を読込
む順序を変えることができ、ソフトウェアを対応して変
更することができる。その他、当業者は、図５のアルゴ
リズムでＹ値を使用するのではなく、台形を同じアルゴ
リズムを使用してＸ軸の代りにＹ軸と平行になるように
構成することができる。これにはすべての「Ｘ」値を「
Ｙ」値にし、「Ｙ」値を「Ｘ」値にするだけでよい。 このような場合には、トラッパは「Ｘ」スタックを備え
ることになり、「ｘｔｏｐ」および「ｘｂｏｔ」の整数
値などを見出すことが必要になる。その上、透視図デー
タＷのような、各頂点に関連する他のデータを、辺ＲＡ
Ｍ３０４にＷデータに対応する余分なビットの読込むよ
う適格に指令することにより、現在のシステムに取入れ
ることができる。更に、多角形プロセッサ２０８および
トラッパ２１０について説明した別々の制御回路を一つ
の処理ユニットに組合せてトラッパを多角形プロセッサ
と関連して動作させるようにすることができる。したが
って、このような修正をすべて次の特許請求の範囲に規
定するように本発明の範囲を包含させるつもりである。

【図面の簡単な説明】

【図１】本発明を組み込んだ変形エンジンを含む図形処
理サブシステムとホストシステムの概念的ブロック図で
ある。

【図２】本発明に基づく台形化回路を含む変形エンジン
の概略図である。

【図３】本発明に基づく台形化回路の一実施例の概略図
である。

【図４】本発明に基づき台形に分割された入力台形を示
している。

【図５】本発明に基づく入力多角形の各セグメントの端
点を決定するためのアルゴリズムである。

【図６】本発明に基づいて入力多角形を台形に分割する
ためのアルゴリズムである。

【符号の説明】 ２０２…入力ＦＩＦＯ ２０４…図形変形プロセッサ、 ２０６…ＦＩＦＯ ２０８…多角形プロセッサ ２１０…台形化回路 ２１２…出力ＦＩＦＯ

Claims (1)

【特許請求の範囲】
1. 【請求項１】表示装置上に表示すべき画像を表す複数の
   多角形であって、それぞれが関連する辺データを備えた
   所定数以下の辺を有する多角形を処理するための装置で
   あって：表示すべき画像の各入力多角形に関して前記辺
   データを提供するための手段と；前記所定数以下の辺を
   有する各入力多角形を、少なくとも１つの台形であって
   、少なくとも２つ以下の辺が前記表示装置の１つの座標
   方向に平行でない３乃至４つの辺を有する閉じた四辺形
   である台形に分解するための台形化手段と；各入力多角
   形の各台形に関する辺データを前記表示装置に出力する
   ための手段と；から成ることを特徴とする装置。