JPH04220780A - 任意の多角形を台形に分解する方法と装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は図形変換エンジンに関し
、特に画像を表す任意の入力された多角形をラスタ走査
変換システムによって、より効率的に表出できる台形へ
と変換するプロセスと装置に関する。

【０００２】

【従来の技術】従来のラスタグラフィックシステムは一
般に２つの個別部品を備えている。即ちユーザの視点に
従って画面の幾何的描写を変換し、照明する図形変換エ
ンジンと、変換された画面を表示画面に表現する表出装
置である。公知のように、画面の幾何的描写は任意の数
の辺を有する複数個の多角形の組み合わせにより構成す
ることができる。換言すると、表示される３次元画像が
異なる陰影の多角形から成る平面として表現されてきた
。ここでいう「多角形」とは順序付けされた頂点Ｖ〔１
〕…Ｖ〔Ｎ〕の集合のことであり、ここにＮは多角形の
頂点のカウントである。これらの頂点は端点がそれぞれ
の頂点Ｖ〔１〕…Ｖ〔Ｎ〕から成る線セグメントＥ〔１
〕…Ｅ〔Ｎ〕である多角形のＮ個の辺を確定する。 例えば、線セグメントＥ〔１〕は端点Ｖ〔１〕及びＶ〔
２〕を有し、一方、線セグメントＥ〔２〕は端点Ｖ〔２
〕及びＶ〔３〕を有する。このような多角形は図形変換
エンジンによって各多角形の頂点の座標（Ｘ，Ｙ，Ｚ）
のような情報及び、各多角形の陰影情報及び全ての画素
レベルの表出計算のために図形変換エンジンで処理され
る命令を含む一連のグラフィックプリミティブとして特
定されることができる。

【０００３】画面のこのような幾何的表現によって画素
画像データを表示装置に表出するのに必要な図形変換エ
ンジンによる処理が容易になる。図形変換エンジンは一
般にこれらのデータにおいて図形の文脈管理、マトリク
ス変換計算、スプラインテセレーション（切り嵌め）及
び照明モデル計算を含む多くのタスクを実行する。変換
エンジンは更にベクトル及び多角形表出ハードウェアの
制御も行う。しかし、このような計算は一般に極めて複
雑かつ時間を要し、多くの処理能力を必要とし、又、そ
の結果として処理が困難なので、従来型のラスタグラフ
ィックシステムで画像が表出される速度に大きな制約が
あることが多かった。

【０００４】前述の問題点を解決するための最も一般的
な提案は図形変換エンジンの処理能力を高めることであ
った。例えば、各多角形を各々並列に処理できるように
複数個の変換エンジンが並列に備えられた。しかし、こ
のようなシステムは極めて複雑かつ高価であり、しかも
効率よく多角形を処理できない。その結果、グラフィッ
クプリミティブ情報の処理効率はこれまで著しく制約さ
れてきた。このように、膨大な数の単純な多角形を含む
複雑な３次元画像でも会話型の速度で表出できるように
、図形変換エンジンの処理効率を高める装置を備えるこ
とが必要である。

【０００５】ベクトル表示システムにおいて、入力され
た多角形を台形に分解することによって画像を表す多角
形を表示画面に表出することが既に提案されている。例
えば、リー氏は「ベクトル表示デバイスにおける領域の
陰影付け」（コンピュータグラフィックス，１５巻３号
，１９８１年８月刊）で図形のベクトル表示システムの
任意の単純な多角形を表示画面に表出するため複数個の
台形に分解する技術を提案している。特にリー氏はＮ個
の頂点を有する任意の単純な多角形の内部を、線間の勾
配と間隔が予め指定された平行線の集合で陰影付けする
アルゴリズムを提唱している。任意の単純な多角形Ｐを
表出するためのリー氏のアルゴリズムはそれぞれの直線
セグメントを形成する頂点の、もしくは不連続の２つの
辺が交差しない（すなわち交差する辺は表出できない）
頂点間の辺の順序付けされたリストとして多角形を表現
する。リー氏が提案する形式のベクトル走査システムで
は陰影付け線は一般に全て水平であるので（すなわち、
陰影付けは多角形の辺の間の複数の水平ベクトルを表出
することにより達成されるので）、入力された多角形は
陰影付けのため複数個の台形に分解される。

【０００６】リー氏の表出システムでは、多角形の頂点
はｙ軸との関連に従って表現される。特に、頂点はそれ
らがｙ方向での極大（しょう乳石状）、ｙ方向での極小
（石荀状）又は規則的な頂点のいずれであるかが定義さ
れる。リー氏はｙ座標に従って多角形の頂点を分類し、
次に各々の頂点が極大、最底点又は規則的頂点のどれで
あるかを吟味する。次に頂点が底から頂まで直線的に走
査され、多角形の内部の臨界線（頂点を通過する水平線
）のセグメント及び辺の連結リストも保持される。連結
リストの辺はこれらの辺と臨界線の交点に基づいて左か
ら右へと順序付けされる。次に、各頂点が走査されると
、出現する頂点の種類に応じて異なる演算が行われる。 このアルゴリズムは最上部の頂点が操作され、又は連結
リストが空になると終了する。

【０００７】

【発明が解決しようとする課題】前述のとおり、リー氏
のシステムはベクトル表示システムに関してだけ開示さ
れており、交差する２つの不連続辺を有しない（即ち辺
が頂点でのみ交差する）単純な多角形の場合だけ動作す
る。更に、リー氏のアルゴリズムは入力多角形の頂点の
各々の分類に準拠しているので、アルゴリズムを実行す
る前に実質的な準備が必要である。その結果、交差する
辺を有する複雑な多角形をリー氏のシステムでは表出で
きない。更に、従来の技術では画素表示システムで点を
表示するためリー氏が教示する技術をどのように利用す
るかが明確ではない。表出システムではどれほど複雑で
あっても十分な速度で任意の入力多角形を表出し、膨大
な数の複雑な多角形を含む複雑な３次元画像も対話型の
速度で表出できることが必要なので、リー氏の表出シス
テムを大幅に改良する必要がある。

【０００８】従って、この分野では交差する辺を含む複
雑な多角形でも真に対話型の速度で処理し、表出できる
多角形表出システムの必要が長期間にわたって痛感され
てきた。本発明はこの要望に応えるために設計されたも
のである。

【０００９】

【課題を解決するための手段】この分野における前述の
長期間にわたる要望は、本発明に従って、図形のラスタ
表示システムが入力多角形をより簡単に操作変換できる
ように任意の多角形を台形に分解する技術によって達成
される。特に、本発明に基づき、多角形は操作方法と平
行な線により境界付けられた隣接領域として定義される
「スラブ」へと分解される。最初に多角形は多角形の全
ての頂点のｙ座標値にて分割される。次に、各スラブご
とにスラブ内にある辺が判定され、許容できない辺の交
差があるかどうかが判定される。そのような辺の交差が
ある場合は、そのスラブは２つのスラブへと分解され、
その各々が別個に処理され、その際、２つのスラブの新
たな分割点は交差点のｙ座標値に出現する。許容できな
い交差点がそれ以上ない場合は、隣接する一対の辺によ
り台形が形成され、ラスタ形成サブシステムへと送られ
る。この技術には僅かな準備しか必要ないので、いかに
複雑であっても任意の入力多角形を表出することができ
る。

【００１０】本発明の好ましい実施例に従って、各多角
形が任意の数の頂点と、関連する辺データを有する対応
する数の辺とを有する、画像を表す複数の多角形を表示
装置に表出する装置が備えられている。本発明に基づく
このような装置は好ましくは任意の数の頂点の座標値、
及び画像の各入力多角形の対応する数の辺の辺データを
含むデータを提供する装置、及び走査方向に垂直な方向
に座標値を増分することにより頂点を分類する装置から
成っている。本発明に基づき、各入力多角形を表示装置
の走査方向と平行な走査領域へと分割するための多角形
プロセッサも備えられている。その際、走査領域は分類
された各々の頂点を通過する線によって走査方向と垂直
な方向で境界付けられている。

【００１１】多角形プロセッサは次に、各走査領域内の
いずれかの辺が交差するかを判定し、次いで、交差する
辺を有する走査領域を、走査方向と垂直な方向の反対端
では分類された各々の頂点を通る線により、又、共通端
では交差する辺の交差点を通る走査方向と垂直な方向の
線により境界付けられた小領域へと細分割する。その結
果生じた走査領域及び各入力多角形の小領域の辺データ
は次に表示装置に表出される。

【００１２】本発明の別な好ましい実施例では、多角形
プロセッサは走査方向と垂直な方向で座標値がより小さ
い、分類された頂点を通る線と各辺が交差する点で座標
値を走査方向に増分することによって各走査領域内の辺
を分類する。更に、各走査領域内の少なくとも２つの辺
が、共通点で走査方向と垂直な方向での座標値がより小
さい頂点を通る線と交差する場合は、多角形プロセッサ
は走査線方向の勾配値を増分することによって辺を更に
分類する。分類された像は次に各々奇数及び偶数記述項
として辺アレイに記憶される。多角形プロセッサは次に
辺アレイ内に奇数記述項として記憶された辺が辺アレイ
内に偶数記述項として記憶された後続の辺と交差する場
合を例外として、交差する辺を含む走査領域用の小領域
を形成する。前記例外は「砂時計」形の台形を直接表出
するラスタサブシステムの能力を活用したものである。 本発明の別の特徴に基づき、表出装置は走査方向と垂直
な方向で所定の厚さ以下である走査領域及び小領域を表
出しない。

【００１３】本発明は更に各多角形が任意の数の頂点と
、関連する辺データを有する対応する数の辺とを有する
、画像を表す複数の多角形を表示装置に表出する方法も
含んでいる。このような方法は本発明に基づき次の段階
から成っている。即ち、任意の数の頂点の座標値と、画
像の各入力多角形の対応する数の辺の辺データとを含む
データを提供し、操作方向と垂直な方向に座標データを
増分することにより頂点を分類し、各入力多角形を表示
装置の走査方向と平行な走査領域へと分解し、その際、
走査領域が分類された頂点を通る線によって走査方向と
垂直な方向で境界付けされており、この段階は各走査領
域内のいずれかの辺が、交差する辺を有する走査領域と
交差し、かつこの走査領域が走査方向と垂直な方向の反
対端では分類された各々の頂点を通る線により、又、共
通端では交差する辺の交差点を通る走査方向と垂直な方
向の線により境界付けられた小領域へと小分割されてい
るかどうかを判定する段階を含んでおり、かつ、各入力
多角形の各走査領域及び小領域の辺データを表示装置に
表出する、各段階である。

【００１４】好ましい実施例に従って、多角形分解段階
は走査方向と垂直な方向で座標値がより小さい、分類さ
れた各々の頂点の一つを通る線と各辺が交差する点で座
標値を走査方向に増分することによって各走査領域内の
辺を分類し、分類された辺を各々奇数及び偶数記述項と
して辺アレイに記憶し、辺アレイ内に奇数記述項として
記憶された辺が辺アレイ内に偶数記述項として記憶され
た後続の辺と交差する場合を例外として、交差する辺を
含む走査領域用の小領域を形成する段階を含んでいる。 更に、多角形分割段階は走査線方向の勾配値を増分する
ことによって辺を分類する段階を含んでおり、互いに交
差する各走査領域内のこれらの辺及び分類された各々の
頂点の一つを通る線は共通点において走査方向と垂直な
方向でより小さい座標値を有している。

【００１５】本発明の方法の別の好ましい実施例は好適
に、処理効率を一層高めるため、表出段階での表出に先
立ち、走査方向と垂直な方向で所定の厚さ以下である走
査領域と小領域を放棄する段階を含んでいる。

【００１６】このように構成された本発明に基づく方法
と装置によって、走査変換システムを通過する台形が従
来型のグラフィック表示システムのラスタ走査変換シス
テムで代表的な多辺の任意多角形よりも大幅に簡単に表
出できるので、処理が著しく促進される。本発明のその
他の利点は本発明の以下の詳細な説明によって明らかに
されよう。

【００１７】

【実施例】ここに開示し、特許請求する本件の発明者は
複雑な任意の入力多角形を後に走査変換システムによっ
て容易に表出できる台形へと分解する多角形プロセッサ
を開発することによって、この分野で長期にわたって痛
感されていた前述の要望を達成したものである。以下の
説明から明らかになるように、本発明の多角形プロセッ
サはシステムの全体的な性能を高めるように入力多角形
を処理する図形変換のサブシステムとして機能する。以
下の説明で明らかになるように、本発明の多角形プロセ
ッサによって比較的短い実行時間で任意の多角形を正し
く表出することができる。更に、スラブ内にある辺の数
に基づいて線形的時間で実行される辺交差検出方法によ
って実行時間は更に短縮できる。次に本発明の好ましい
実施例に基づく前記、及びその他の有利な特徴を備えた
プロセスを図１ないし図３を参照しつつ説明する。当業
者にはここに開示する説明は例示を目的とするに過ぎず
、本発明の範囲を限定するものではないことが明白であ
ろう。本発明の範囲に関する疑問は全て添付の特許請求
の範囲を参照することによって解決できる。

【００１８】前述の継続中の１９９０年３月１４日出願
の米国特許出願第４９３１８５号に記載されているよう
に、ここに開示される多角形プロセッサは一般に辺勾配
計算及びサブ−画素調整、及び下流のハードウェアに命
令を発する任務を負っている。しかし、本発明に基づき
、多角形プロセッサは更に入力多角形を表示画面の座標
方向と平行な一つ又は二つの辺を有する台形へと分解す
る機能も果たす。好ましい実施例では所定の辺数よりも
辺が少ない多角形の場合は前述の関連出願に開示されて
いる台形化回路によって更に効率よく処理されるものの
、基本的に全ての入力多角形は本発明の多角形プロセッ
サによって台形に分割することができる。

【００１９】本発明の多角形プロセッサは「台形化」と
称するプロセスによって、プロセッサが受けた辺データ
から台形を作成する。ここで述べる「台形化」とは入力
多角形を表示装置の座標軸と平行な一つ又は二つの辺を
有する単数又は複数の台形領域へと細分化するプロセス
を意味し、その場合、台形の上角又は下角が縮退してい
る場合、即ち三角形の場合のように単一の点である場合
は一つの辺だけが座標軸と平行である。本発明に基づき
、台形化は入力多角形が膨大な数の交差辺を有している
場合でも、任意の数の頂点を有する入力されたどのよう
な多角形においても実行できる。本発明の技術の唯一の
制約は表出システムの容量である。例えば、本発明を砂
時計形の台形を許容する表出システムと共に利用するも
のとして以下説明する。しかし、当業者には本発明の技
術は交差辺がない台形は表出しない表出システムにも利
用できることが了解されよう。

【００２０】本発明の実施例を図１ないし図３を参照し
つつ説明する前に、動作の原理及び使用される定義の幾
つかを簡単に説明する。

【００２１】閉じた領域を表す入力された多角形におい
ては、多角形は偶数の巻数（ｗｉｎｄｉｎｇ　ｎｕｍｂ
ｅｒ）を有していなければならず、その場合、巻数は光
線が所定方向で多角形を横切って投射された時に放射光
線が交差する辺数と対応する。換言すると、閉じた多角
形を通る光線はいずれも偶数個の辺と交差しなければな
らず、ひいては偶数の巻数を有していなければならない
。従って、複雑な入力された多角形が平行な光線で境界
付けされた複数の領域へと分割される場合は、各領域内
に多角形の偶数個の辺があることになる。本出願におい
てはこれらの領域を「スラブ」といい、そこでは投射光
線は走査方向に平行であり、入力された多角形をそれぞ
れのスラブへと区分する。入力された多角形の各スラブ
はこのように走査線と垂直な方向（以後「Ｙ−方向」と
呼ぶ）でスラブの境界を形成する光線の点の座標値によ
って確定することができる。これらの値はここではスラ
ブの頂を確定する光線の点のｙ座標値であるｙ頂点値、
及びスラブの底点を確定する光線の点のｙ座標値である
ｙ底点値と称する。

【００２２】このように、各スラブは入力された多角形
の複雑さに応じて交差し、又は交差しない偶数の辺（以
後「作用辺」と呼ぶ）を含んでいる。前述したとおり、
スラブ内の連続的な作用辺はスラブ内で互いに交差する
ことがある。辺が対偶であり、従ってスラブ内に砂時計
状の台形領域を形成する場合、これは問題にはならない
。このような領域は頂点の順序付け及び多角形の「内側
」を形成する辺の辺を定めることによって正しく表出さ
れ、かつ陰影付けすることができる。しかし、交差する
不連続の辺を有するスラブは表出回路にとって問題を生
ずる。何故ならば、辺に関する適正な表出属性を判定す
ることが困難だからである。（即ち、所定の画素が多角
形の内側にあるのか外側にあるのかを判定することが困
難である。）このようなスラブの場合は、作成された台
形は砂時計状ではなく、Ｙで凹状であり、このＹ凹面は
走査線内に２つ以上の辺が存在する多角形の特性である
。

【００２３】例えば、複雑な多角形が所定の光線に沿っ
てＹで凹状であり、この光線について巻数４を有してい
ると想定すると、光線が交差する辺には順次ラベルＥ＝
１，２，３及び４を割り当てることができる。光線に沿
って最初に遭遇する辺Ｅ＝１は光線に沿って二番目に遭
遇する辺Ｅ＝２と交差し、その結果生ずる台形は砂時計
状となろう。しかし、辺Ｅ＝１が辺Ｅ＝３と交差すると
、その結果生ずる領域は単一の台形としては表出できな
いであろう。同じ理由により、辺Ｅ＝２は辺Ｅ＝１と交
差するが、辺Ｅ＝３又はＥ＝４とは交差し得ない。何故
ならば、辺Ｅ＝２は辺Ｅ＝１との間に陰影領域を形成す
るため辺Ｅ＝１と対偶にされているからである。従って
、光線と遭遇する最初の辺をＥ＝１と定義すると、偶数
番号の辺と次の奇数番号の辺とが辺の対偶を形成するの
で、偶数番号の辺は奇数番号の辺と交差するが、他の辺
の交差は許容されず、ここでは「不的確な」交差と呼ぶ
。この区別は図３を参照した説明で更に明らかになろう
。

【００２４】本発明の多角形プロセッサは多角形を台形
へと分解する前に多角形に関する全ての必要なデータを
受けなければならない。このデータには各頂点の頂点座
標及び各辺の属性が含まれる。このデータを受けると、
多角形プロセッサは台形を作成する段階に進行する。後
述するように、多角形プロセッサは次にｙ値によって頂
点を分類し、分類された頂点を順次比較して、それぞれ
のスラブにおける頂及び低のｙ値を判定する。多角形デ
ータは多角形及び辺のアレイを確定するそれぞれの頂点
として受けられるものと想定されている。この辺アレイ
内の辺は吟味されるスラブと交差すると作用辺になる。 更に、可変的なＸ頂点はそれが現在のスラブの頂点（ｙ
頂点）と交差する点で辺のｘ座標と対応し、一方、可変
的なｘ底点はそれが現在のスラブの底点（ｙ底点）と交
差する点で辺のｘ座標と対応する。最後に、ｘ勾配は辺
の勾配と対応し、Δｘ／Δｙによって定義される。後述
するように、作用辺はＸ頂点の値を増分することによっ
て分類され、その結果線はｘ勾配を増大することによっ
て区切られる。

【００２５】さて、本発明に基づき台形化を実施するた
め多角形プロセッサによって実行されるアルゴリズムの
詳細を図１ないし図３を参照しつつ説明する。

【００２６】図１は本発明に基づく台形化アルゴリズム
を図示している。処理は段階１００で開始され、入力さ
れた多角形の頂点のアレイが段階１０２−１０８で多角
形プロセッサに読み込まれる。特に、頂点の入力アレイ
は段階１０２で０に等しいアレイ変数Ｖを設定し、次に
段階１０４で変数Ｖを入力された多角形の頂点数に対応
する頂点のカウントと比較することによって読み込まれ
る。全ての頂点が未だ読み込まれていない場合は、処理
は段階１０６に進行し、そこで頂点アレイ内の現在の頂
点のｙ座標がｙ値アレイの対応するｙ値へと読み込まれ
る。次にアレイ変数Ｖが段階１０８で増分され、ループ
が次の記述項をｙ値アレイへの読み込みを反復できるよ
うにされる。全ての頂点のｙ値が読み込まれると、制御
は段階１１０に進行し、そこで可変的ｙカウントが現在
の頂点カウントに割り当てられる。次にｙ値アレイの値
が段階１１１で、例えば本出願の出願人に譲渡され、本
明細書に参考文献として全面的に組み入れられた１９９
０年２月９日出願の米国特許出願第４７８１２６号に開
示されている高速分類スタックを利用して分類される。

【００２７】段階１１２では、ｙ値アレイ内の最初の値
が現在のスラブのｙ頂点の値として割り当てられ、次に
段階１１４でループカウンタＶが１に設定される。次に
段階１１６ないし１３８がｙ値アレイ内の各記述項につ
いて実行される。特に、ループカウンタＶが段階１１６
でｙカウントの値と比較され、ループの変数がｙカウン
トの値以上又はこれと等しい場合は、ｙ値アレイ内の全
ての記述項が読み込まれたことを示し、段階１１８で処
理は終了する。そうではない場合は、ｙ底点値が段階１
２０でｙ値アレイ内の次の値に割り当てられる。次に段
階１２２でそれぞれのｙ底点及びｙ頂点がｙ座標とほぼ
等しいかどうかが点検され、そうである場合は、新たな
スラブは作成されない。換言すると、ｙ値アレイ内のそ
れぞれの頂点のｙ座標が同一である、即ち例えば互いに
一つの走査線内にある場合は、このような小さいスラブ
の作成は小さすぎて表出の実行時間が無駄であるものと
判定される。このような場合は、制御は段階１２４に進
み、そこでｙ頂点がｙ底点と等しい値に設定され、次に
ループカウンタＶが段階１２６で増分される。スラブが
小さすぎない場合は（即ちｙ頂点がＹ底点とほぼ等しく
ない場合）、制御は段階１２８に進む。

【００２８】段階１２８ではｙ頂点とｙ底点の間の作用
辺のリストが判定される。前述のとおり、作用辺とは走
査線と平行なｙ頂点とｙ底点を通る光線により確定され
たスラブと交差する辺である。次に段階１３０で作用辺
はｘ頂点の値を増分することによって（即ち、スラブの
頂部で増大するｘ方向に進行する光線が作用辺と交差す
る位数で）辺アレイへと分類される。特に、作用辺がｙ
頂点を通る光線と交差するｘ頂点の値が決定され、辺は
ｘ頂点の位数を増分することによって分類される。各々
の辺がｘ頂点について同じ値を有している場合は、結合
線はｘ勾配の値を考慮することによって区切られる。例
えば、２つの辺がｘ頂点について同じ値を有している場
合は、増分するｘ頂点の方向で分類する際、ｘ頂点につ
いてより正の値を有する辺が最初に遭遇する辺として選
択される。

【００２９】作用辺がｘ頂点の値を増分することによっ
て分類された後、段階１３２で現在のスラブに「不的確
」な交差が存在するかどうかが判定される。前述のとお
り、「不的確」な交差とは一対ではない作用辺がスラブ
内で互いに交差することである。図２を参照して後述す
るように、このような「不的確」な交差が現在のスラブ
内に存在しない場合は、スラブ内の台形が段階１３４で
表出され、ループは反復される。しかし、段階１３２で
「不的確」な交差が発見された場合は、現在のスラブは
２つ又はそれ以上のスラブに分割される。次にスラブの
分離点でのｙ座標が段階１３６でｙ値アレイ内の現在位
置に挿入され、段階１３８でｙ値アレイ内の追加値を考
慮に入れるためｙカウントが増分され、ループは反復さ
れる。次に図２を参照しつつ交差が「不的確」な交差で
あるかどうかを判定するアルゴリズムの例を説明する。

【００３０】「不的確」な交差を判定するアルゴリズム
は段階２００で開始され、段階２０２で、分類された作
用辺アレイ内の第１の辺のｘ底点値が分類された作用辺
アレイ内の第２の辺のｘ底点値未満であるかが判定され
る。次に段階２０４又は２０６で可変フェンスがより大
きいｘ底点の値を有する辺として確定される。次に段階
２０８でループカウンタ「カウント」が２に設定され、
段階２１０ないし２２６で辺アレイ内の残りの一対の辺
が辺「フェンス」と比較され、それらが交差するかどう
かが判定される。

【００３１】段階２１０でカウント値が現在のスラブ内
の作用エッジ数以上であるか、等しいかどうかが判定さ
れ、そうである場合は、処理は図１の段階１３４に進行
して台形を作成することができる。そうではない場合は
、処理は段階２１２に進行し、そこで現在の辺はｘ底点
の値が辺フェンスのｘ底点の値未満であるかどうかが判
定される。換言すると、現在の辺が以前の辺対の右端と
交差するかどうかが判定される。これらの辺が実際に交
差している場合は、それは「不的確な」交差であり、段
階２１４で、例えば交差する辺のｘ頂点の値の差を交差
する辺のｘ勾配値の差で除算し、かつインターセプト値
（ｙ頂点）を加算することによる交差辺方程式を同時に
解くことによって、これらの辺のｙ交差（ｙ分割）が確
定される。一方、現在の辺のｘ底点値が段階２１２の辺
フェンスでのｘ底点値未満ではない場合は、処理は段階
２１６に進行し、そこで次の辺が辺フェンスと交差する
かどうかが判定され、そうである場合は、段階２１８で
段階２１４と同様に、これらの辺のｙ交差（ｙ分割）が
確定される。次に、段階２１２又は２１６でｙ分割が計
算されると、前述のようにｙ分割の値を現在のアレイ位
置に挿入し、かつ後続の全てのアレイ値をバンプするこ
とによって、ｙ分割の値が段階１３６（図１）で、現在
のアレイ位置でのｙ値へと挿入される。更に、追加のｙ
値がこのようにｙ値アレイに挿入されるので、ｙカウン
トの値は処理が反復される前に段階１３８で増分されな
ければならない。このようにして、現在のスラブは共通
の辺ｙ分割を有する二つのスラブへと分割される。

【００３２】段階２１２及び２１６でそれぞれの辺が交
差しないことが判定されると、段階２２０で現在の辺対
のどれがｘ底点における右端の値を有しているかが判定
される。次にこの辺は段階２２６でカウントが増分され
る前に、段階２２２又は段階２２４で辺フェンスとして
確定され、処理は次の一対の辺及び新たな辺フェンスに
ついて反復される。この処理は現在のスラブ内の全ての
辺対が吟味されるまで反復される。

【００３３】次に図３を参照しつつ図１及び図２のアル
ゴリズムを説明する。図３は交差辺を有する複雑な任意
多角形を示し、辺の幾つかは砂時計状の台形を処理でき
る表出回路にとって受け入れられるものであり、他の辺
は受け入れられない辺である。図示のとおり、複雑な多
角形は頂点のアレイＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，
Ｉ，Ｊ及びＫによって定義され、これらの頂点は隣接す
る頂点として前述した順序の入力であり、入力アレイ内
の隣接する頂点は多角形の同じ辺の端点を確定する。多
角形内部の画素には陰影が付けられ、一方、多角形の外
側の画素には付けられていない。図３の多角形の場合、
入力頂点アレイは次のように現れる。

【００３４】 　　頂点アレイからのｙ座標は段階１０４、１０６及び
１０８でｙ値アレイに読み込まれるので、次のｙ値アレ
イが生ずる。

【００３５】 　　次に段階１１０でｙカウントが頂点カウント（１１
）に等しく設定され、段階１１１でｙ値アレイが分類さ
れる。図３の多角形について分類されたｙ値アレイは次
のとおりである。

【００３６】 　　段階１１２でｙ頂点の値がｙ値アレイの第１の記述
項（Ｙ０）に等しく設定される。次にループに入り、ｙ
底点の値はｙ値アレイ内の次の記述項（Ｙ０）として設
定される。しかし、ｙ項点はｙ底点と等しくないので、
段階１２２でスラブが小さすぎるものと判定され、ルー
プカウンタが段階１２６で増分される。ｙ頂点は依然Ｙ
０と等しいが、ｙ底点は段階１２０での次のループ反復
中にｙ値アレイ（Ｙ１）内の次の値に割り当てられる。 このようにしてＹ０及びＹ１がスラブ１を確定し、処理
は段階１２８に進行してスラブ１内の作用辺のリストが
作成される。

【００３７】スラブ１内の作用辺は図３に示す辺ＩＪ，
ＪＫ，ＥＦ及びＦＧである。これらの辺は段階１３０で
前述の分類原理に基づいてＩＪ，ＪＫ，ＥＦの順に分類
される。次に図２のアルゴリズムに従って辺のいずれか
が交差するかどうか判定される。どの辺も交差しないの
で、処理は段階１３４に進み、そこで三角形ＩＪＬとＥ
ＦＭで形成された台形が作成される。次にループカウン
タが増分され、ｙ値アレイからの次の値が次のループ反
復中にｙ底点として割り当てられる。ｙ値〔３〕（Ｙ１
）はｙ値〔２〕と同一であるので、段階１２２でスラブ
は小さすぎるものと判定され、ループカウンタは再度増
分される。ｙ値〔４〕もｙ値〔３〕と等しいので、再び
スラブは小さすぎるものと判定され、次のｙ値が読み込
まれるようにループカウンタが再度増分される。しかし
、ｙ値〔５〕はＹ３と等しいので、処理は段階１２８に
進み、スラブ２内の作用辺のリストが作成される。 （Ｙ１とＹ３の間）次に作用辺は前述のようにｘ頂点を
増大することによって分類され、その結果生じたアレイ
は次のとおりである。

【００３８】 　　次に段階１３０で図２のアルゴリズムに基づき、前
記の辺アレイのいずれかの辺が互いに交差するかどうか
判定される。最初に段階２０２で辺ＡＢのｘ底点が辺Ｋ
Ａのｘ底点以下であるかが判定される。辺ＡＢのｘ底点
（Ｘ０）が辺ＫＡのｘ底点（Ｘ４）未満であるので、段
階２０６で辺フェンスが辺ＫＡ（右端の辺）として割り
当てられる。次に段階２０８でカウントが２に設定され
、段階２１２で次の辺、即ち辺〔２〕（ＨＩ）がｘ底点
（Ｘ６）について、辺ＫＡにおけるｘ底点の値よりも大
きい値を有していることが判定される。同様にして段階
２１６で辺ＪＫがｘ底点（Ｘ６）について、辺ＫＡにお
けるｘ底点の値よりも大きい値を有していることが判定
される。従って、辺ＨＩと辺ＪＫはスラブ２内の辺ＫＡ
と交差しない。次に辺フェンスアレイが現在の辺対の右
端の辺（ＨＩ）として再度割り当てられ、ループカウン
タは次の辺対を読み込むため２だけ増分される。

【００３９】ループの次の反復中、段階２１２で辺〔４
〕（ＤＥ）が辺ＨＩとは交差しないことが判定される。 しかし、段階２１６では、辺ＦＧが辺ＨＩ（Ｘ１２）に
おけるｘ底点値未満の値をｘ底点において有しているの
で（Ｘ９）、辺〔５〕（ＦＧ）が辺ＨＩと交差すると判
定される。辺ＦＧとＨＩの間の交差点は次に段階２１８
でｙ分割（Ｘ１１，Ｙ２）として判定される。次に処理
は段階１３６に進行して、図３に示すようにスラブ２を
スラブ２Ａとスラブ２Ｂとに分割するため、新たなスラ
ブ境界のｙ分割を挿入できるようにする。そこでｙ値ア
レイは次のようになる。

【００４０】 　　次に処理はｙ頂点＝Ｙ１及びＹ底点＝Ｙ２により確
定されたスラブ（スラブ２Ａ）について反復される。処
理段階はこのようにして、全てのスラブ（ひいては全て
の多角形）が表出されるまで、Ｙ−値アレイ内の残りの
値について進行する。

【００４１】当業者には隣接しない辺が交差するので、
前述のアルゴリズムがスラブ２をスラブ２Ａと２Ｂに分
割することが了解されよう。前述のとおり、この実施例
の表出システムは台形ＯＩＬＮ及びＯＭＥＰのような砂
時計状の台形を処理できるので、辺ＨＪとＪＫ及び辺Ｄ
ＥとＦＧの交差は「不的確な」交差としては扱われない
。しかし、表出回路と適応させるために必要ならば、こ
のような交差を全て「不的確な」交差として扱い、スラ
ブ２を幾つかのスラブに分割してもよい。当業者には更
に、前述のアルゴリズムは図示した多角形にだけ適用さ
れるものではなく、任意の数の入力頂点及び任意の数の
交差辺を有する多角形に適用できることが明白であろう
。

【００４２】

【発明の効果】これまで説明した多角形プロセッサ及び
台形化技術は、辺が少ない多角形では準備が少なくて済
み、一方、より複雑な多角形の場合は交差検出処理がス
ラブ内にある辺の数に基づき直線的な時間で実行される
ので実行時間を最小限にすることができ、効率は著しく
促進される。更に、本発明はいかに複雑であろうとも、
どのような多角形をも表出できる点で公知の技術を改良
したものである。

【００４３】これまで本発明の単一の実施例を詳細に説
明してきたが、当業者には本発明の新規の教示と利点か
ら逸脱することなく、多くの修正が可能であることが了
解されよう。例えば、入力された多角形の頂点が読み込
まれる順序を変更し、それに対応してソフトウェアを変
更することができる。更に、当業者には図２及び図３の
アルゴリズムにおいてＹ座標を用いないで、同じアルゴ
リズムでＸ軸ではなくＹ軸と平行になるように台形を構
成することができることが明白であろう。そのために必
要であるのは、「Ｘ」値の全てが「Ｙ」値になり、「Ｙ
」値の全てが「Ｘ」値になることだけである。このよう
な場合は、スラブを確定するため、「ｙ頂点」及び「ｙ
底点」ではなく、「ｘ頂点」及び「ｘ底点」を発見する
ことが必要であろう。更に、砂時計状の台形を表出でき
ない表出システムの場合は、スラブを前述のような不連
続の交差ではなく、任意の交差辺について分割してもよ
い。更に、アルゴリズムを最小限修正することによって
、ｘ底点及びｙ底点を計算しなくても頂点のＸ−及びｙ
値を利用することができる。更に、本発明は前述の１９
９０年２月９日出願の米国特許出願第４７８１２６号に
開示されている台形化回路と組み合わせて、より効率が
高い単一の処理装置として構成することもできる。 従って、これらの修正は全て以下の特許請求の範囲に含
まれるものである。

【図面の簡単な説明】

【図１】本発明に基づき、任意の多角形から台形を形成
するためのアルゴリズムを示している。

【図２】スラブ内で辺が交差しているかどうかを判定し
、交差している場合には、現状の「スラブ」を２以上の
スラブに分割するためのアルゴリズムを示している。

【図３】本発明に基づいて、台形に分割された複雑な入
力多角形を示している。

Claims (1)

【特許請求の範囲】
1. 【請求項１】画像を表す複数の多角形を表示装置に描く
   ための装置であって、各多角形は任意の数の頂点と関連
   する辺データを備えた対応する数の辺を備え：前記画像
   の各入力多角形に関する前記任意の数の頂点と前記対応
   する数の辺の前記辺データの座標値を含むデータを発生
   するための手段を備え；走査方向に垂直な方向に座標値
   を増加することにより前記頂点を分類するための手段を
   備え；多角形プロセッサは各入力多角形を前記表示装置
   の走査方向と平行な走査領域に分割し、前記走査領域は
   分類された各頂点を通過する線によって前記走査方向に
   垂直な方向で境界付けられており、その際、前記多角形
   プロセッサは各走査領域内のどの辺が交差するかを判定
   し、次いで、交差辺を備えた走査領域を、前記走査方向
   に垂直な前記方向の反対端では分類された各頂点を通る
   線及び、共通端では前記交差辺の交差点を通る前記走査
   方向に垂直な方向の線により境界づけられた小領域に細
   分割し；さらに、各走査領域及び各入力多角形の小領域
   に関する辺データを前記表示装置に描くための手段が設
   けられて成ることを特徴とする装置。