JPH04184688A - 平面ポリゴンの境界点発生装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〈産業上の利用分野〉 この発明は平面ポリゴンの境界発生装置に関し、さらに
詳細にいえば、平面ポリゴンのぬりつぶし描画を行なう
場合にぬりつぶし方向の始点、終点となる境界を発生す
るための装置に関する。

〈従来の技術〉 従来から、図形描画を行なうに当って、任意の形状の図
形を複数の三角形ポリゴンに分割し、得られた各三角形
ポリゴンについてぬりつぶし処理を施すようにした図形
描画装置が提供されている。

この図形描画装置においては、ぬりつぶし対象図形が全
て三角形ポリゴンであり、三角形ポリゴンは必ず平面で
あるから、図形描画装置による描画処理を行なう前に、
ぬりつぶし方向の勾配および稜線方向の勾配を得ておき
、予め得られている三角形ポリゴンの頂点データおよび
勾配データに基づいて稜線補間演算およびぬりつぶし補
間演算をこの順にパイプライン処理する構成が採用され
る。

具体的には、頂点データまたは累積加算データを保持す
る累積加算値用レジスタ（７１）および勾配を保持する
勾配レジスタ（７２）の内容を加算器（７３）に供給し
、加算結果を累積加算値用レジスタ（７１）にフィード
バックするとともに、累積加算値用レジスタ（７１）の
内容を稜線累積加算結果として出力する。そして、初期
値としての稜線累積加算結果または累積加算データを保
持する累積加算値用レジスタ（７４）および勾配を保持
する勾配レジスタ（７５）の内容を加算器（７６）に供
給し、加算結果を累積加算値用レジスタ（７４）にフィ
ードバックするとともに、累積加算値用レジスタ（７４
）の内容をぬりつぶし累積加算結果として出力する。尚
、８カされるぬりつぶし累積加算結果は表示のための整
数格子に適合させるべく整数値として出力される。

〈発明が解決しようとする課題〉 上記従来の図形描画装置は隣合う平面ポリゴンの描画を
行なう場合において境界部における描画ピクセルが同じ
になってしまうので、表面ポリゴンと裏面ポリゴンとの
突き合せ部において、描画順序によっては裏面ポリゴン
が最終的に描画されてしまい、図形全体としての描画品
質を低下させてしまうという不都合がある。

また、ラスター・オペレーションのようなピクセル単位
の演算を行なう場合には、同一ピクセルについて複数回
ピクセル単位の演算を行なうことになり、所期の演算結
果が得られるという保証がなくなってしまうという不都
合がある。

〈発明の目的〉 この発明は上記の問題点に鑑みてなされたものであり、
隣合う平面ポリゴンの境界部においてそれぞれ該当する
平面ポリゴンの内部に含まれる点を境界として発生する
ことができる平面ポリゴンの境界発生装置を提供するこ
とを目的としている。

く課題を解決するための手段〉 上記の目的を達成するための、第１の発明の境界発生装
置は、平面ポリゴンの稜線補間データまたはぬりつぶし
累積加算値を保持する累積加算値保持手段と、ぬりつぶ
し方向の勾配値を保持する勾配値保持手段と、小数部切
り上げ用の定数値を保持する第１定数値保持手段と、小
数部を切り上げて１だけ減算するための定数値を保持す
る第２定数値保持手段と、勾配値保持手段、第１定数値
保持手段および第２定数値保持手段の内容を選択する選
択手段と、累積加算値保持手段の内容と選択手段により
選択された内容とを加算して再び累積加算値保持手段に
供給する加算手段とを含んでいる。

但し、勾配値保持手段、第１定数値保持手段および第２
定数値保持手段がマルチポート・レジスタ・ファイルま
たはマルチポート・メモリであることが好ましい。

第３の発明の境界発生装置は、平面ポリゴンの稜線補間
データまたはぬりつぶし累積加算値を保持する累積加算
値保持手段と、ぬりつぶし方向の勾配値を保持する勾配
値保持手段と、小数部切り上げ用の定数値を保持する第
１定数値保持手段と、小数部を切り上げて１だけ減算す
るための定数値を保持する第２定数値保持手段と、累積
加算値保持手段、第１定数値保持手段および第２定数値
保持手段の内容を選択する選択手段と、勾配値保持手段
の内容と選択手段により選択された内容とを加算して再
び累積加算値保持手段に供給する加算手段とを含んでい
る。

く作用〉 第１の５発明の境界発生装置であれば、稜線補間により
得られた２点間の補間演算を行なって整数格子上のぬり
つぶし画素を得る場合において、最も左側のぬりつぶし
画素については、選択手段により第１定数値保持手段の
内容を選択して加算手段により加算して稜線上または稜
線よりも右側、即ち描画対象である平面ポリゴンの内部
のぬりつぶし画素を得ることができる。その後は、選択
手段により勾配値保持手段の内容を選択して累積加算を
行なうことにより順次ぬりつぶし画素を得ることができ
る。そして、最も右側のぬりつぶし画素については、選
択手段により第２定数値保持手段の内容を選択して加算
手段による加算を行なわせることにより、稜線上または
稜線よりも左側、即ち描画対象である平面ポリゴンの内
部のぬりつぶし画素を得ることができる。

以上の説明から明らかなように、隣合う平面ポリゴンの
全てについて該当する平面ポリゴン内部のぬりつぶし画
素のみを発生できるので、境界を共有するという不都合
を解消できる。即ち、従来の境界発生方法では、稜線を
共有している関係上、隣合う平面ポリゴンについて共通
する稜線上のぬりつぶし画素は、一方の平面ポリゴンに
関して平面ポリゴンの内部になれば、他方の平面ポリゴ
ンに関して必ず平面ポリゴンの外部になっていたので、
表面ポリゴンと裏面ポリゴンとの突き合せ部において描
画順序によっては裏面ポリゴンが表示されてしまうとい
う不都合かあり、また、ぬりつぶし画素単位の演算を行
なうピクセル・オペレーション等においては、同一のぬ
りつぶし画素について複数回の演算を行なうことによっ
て所期の演算結果が得られなくなる可能性があるという
不都合があったが、この発明においては、このような不
都合を確実に解消できる。

第２の発明の境界発生装置であれば、マルチポート・レ
ジスタ・ファイルまたはマルチポート・メモリから該当
する内容を選択して読み出すだけでよいから構成を簡素
化でき、しかも第１の発明と同様の作用を達成できる。

第３の発明の境界発生装置であれば、平面ポリゴンの稜
線補間データを加算手段を通して初期値として累積加算
値保持手段に供給するに当って選択手段により第１定数
値保持手段の内容を選択して加算手段による加算を行な
うのであるから、ぬりつぶし描画開始側の境界発生を高
速に達成でき、全体としての描画速度を高速化できる。

〈実施例〉 以下、実施例を示す添付図面によって詳細に説明する。

第１図はこの発明の境界発生装置を組み込んだ図形描画
装置の一実施例を示すブロック図であり、稜線補間結果
を初期値として保持する累積加算値レジスタ（１）と、
平面ポリゴンのぬりつぶし方向の勾配値を保持する勾配
値レジスタ（２）と、累積加算値レジスタ（１）の内容
に勾配値を累積加算して加算結果を累積加算値レジスタ
（１）にフィートノ（・ツクする加算器（３）と、小数
部切り上げ用の定数値“００００、ＦＦＦＦ　（ＨＥＸ
）’を保持する第１定数値レジスタ（４）と、小数部を
切り上げて１だけ減算するための定数値“ＦＦＦＦ、Ｆ
ＦＦＦ　（ＨＥＸ）”を保持する第２定数値レジスタ（
５）と、稜線補間結果または加算結果を選択して累積加
算値レジスタ（１）に供給するマルチプレクサ（６）と
、勾配値レジスタ（２）の内容、第１定数値レジスタ（
４）の内容、または第２定数値レジスタ（５）の内容を
選択して加算器（３）に供給するマルチプレクサ（７）
とを有している。

上記構成のぬりつぶし補間装置の動作は次のとおりであ
る。尚、以下の説明においては、平面ポリゴンの左稜線
から右稜線に向かってぬりつぶし補間演算を行なうよう
にしている。

先ず、マルチプレクサ（６）を介して累積加算値レジス
タ（１）に稜線補間結果が供給されるとともに、勾配値
レジスタ（２）にぬりつぶし方向の勾配値が供給される
ことにより初期設定が完了する。

次いで、マルチプレクサ（７）により第１定数値しジス
タ（４）の内容が選択され、稜線補間結果と共に加算器
（３）に供給されるので、稜線補間結果が整数格子上の
値である場合を除いて小数部を切り上げた加算結果を得
ることができ、この加算結果をマルチプレクサ（６）を
介して累積加算値レジスタ（１）にフィードバックする
。即ち、この処理によって、稜線上、または稜線に最も
近い平面ポリゴン内部の整数格子点を整数部に有する値
が累積加算値レジスタ（１）に保持される。

その後は、マルチプレクサ（７）により勾配値レジスタ
（２）の内容が選択され、従来装置と同様に順次補間結
果を得ることができる。

そして、ぬりつぶし終了点の値を得る場合には、マルチ
プレクサ（７）により第２定数値レジスタ（５）の内容
が選択され、累積加算値と共に加算器（３）に供給され
るので、稜線補間結果が整数格子上の値である場合を除
いて小数部を切り上げて１だけ減算した加算結果を得る
ことができる。即ち、この処理によって、稜線上、また
は稜線に最も近い平面ポリゴン内部の整数格子点を整数
部に有する値が累積加算値レジスタ（１）に保持される
。

尚、上記累積加算値レジスタ（１）の内容はそのままぬ
りつぶし方向の補間結果として出力され、小数部の切り
捨て処理が施された状態で図示しない画像メモリに供給
される。したがって、平面ポリゴンの状態の如何に拘ら
ず、ぬりつぶし方向の補間結果として平面ポリゴン内の
格子点上の値を出力でき、隣合う平面ポリゴンとの境界
部において格子点上の画素を共有するという不都合を解
消できる。

第２図は奥行き値（以下、ｚ値と称する）の補間演算を
行なう補間演算部の構成を示すプロ・ツク図であり、初
期値および勾配値を保持するマルチポート・レジスタ・
ファイル（１１）と、マルチポート・レジスタ・ファイ
ル（１１）からの読み出しデータをシフトさせる双方向
シフト・レジスタ（１２）と、稜線補間時の累積加算結
果を保持する稜線用累積加算結果レジスタ（１３）と、
ぬりつぶし方向補間時の累積加算結果を保持するぬりつ
ぶし用累積加算結果レジスタ（１４）と、双方向シフト
φレジスタ（１２）の内容または“０°データを選択す
るマルチプレクサ（１５）と、上記累積加算結果レジス
タの内容または“Ｏ°データを選択するマルチプレクサ
（１Ｂ）と、マルチプレクサ（１５）により選択された
データおよびマルチプレクサ（１６）により選択された
データに基づく加算を行なう加算器（１７）と、加算結
果を一時的に保持するパイプライン・レジスタ（１８）
とを有している。尚、加算結果は、何れかの累積加算結
果レジスタに供給される。

第２図の構成の補間演算部の動作を、第３図および第４
図のタイミング・チャートを参照しながら以下に説明す
る。

（１）　　ｚ値の補正を行なわない場合但し、第３図（
Ｇ）に示す三角形ポリゴンの場合について説明する。

この場合には、第３図（Ｂ）に示すようにマルチボート
・レジスタ・ファイル（１１）から先ず初期値ｚ００が
読み出され、次いで、同図（Ｃ）に示すように双方向シ
フト・レジスタ（１２）から初期値ｚ００がそのまま出
力される。この場合には、マルチプレクサ（１６）によ
り“０′データが選択されるので、両累積加算結果レジ
スタに初期値ｚｏＯが供給されるとともに、パイプライ
ン・レジスタ（１８）にも初期値ｚ００が供給され、次
のクロック・タイミングでそれぞれ出力される（同ＩＮ
　（Ｄ）　　（Ｅ）（Ｆ）参照）。

その後は、同図（Ｂ）に示すように、マルチボート・レ
ジスタ・ファイル（１１）が２方向の勾配値ｄ　ｚ　／
　ｄ　ｘを出力し続けるとともに、同図（Ｃ）に示すよ
うに、双方向シフト・レジスタ（１２）も上記勾配値ｄ
ｚ／ｄｘを出力し続け、さらに同図（Ｄ）に示すように
、稜線用累積加算値レジスタ（１３）が上記初期値ｚ０
０を出力し続ける。そして、マルチプレクサ（１６）に
よりぬりつぶし用累積加算値レジスタ（１４）の内容を
選択して累積加算を行なうことにより、ぬりつぶし方向
の２値ｚ　０１．　　ｚ　０２゜ｚ　０３．　　ｚ　０
４．　　ｚ　０５を順次得ることができる（同図。

（Ｅ）（Ｆ）参照）。

ぬりつぶし方向の補間演算が終了した後、即ち、２値ｚ
０５が得られた後は、双方向シフト・レジスタ（１２）
を通してマルチボート・レジスタ・ファイル（月）から
稜線方向の勾配値ｄｚ０２／ｄｙ０２が出力され、稜線
用累積加算値レジスタ（１５）の内容ｚＤＯが出力され
るので、加算器（１７）によって加算することにより次
のぬりつぶし方向の２値の初期値ｚｌＯが得られる。そ
して、得られた初期値ｚｌＯおよび上記勾配値ｄ　ｚ　
／　ｄ　ｘに基づいて累積加算動作を行なうことにより
、次のぬりつぶし方向の２値ｚ　１１．　　ｚ　１２・
・・を順次行ることができる。

尚、第３図（Ａ）はクロック信号出力を示す。

その後は、上記一連の動作を反復することにより、平面
ポリゴンの全範囲の２値を得ることができる。

（Ｉｌ）　　ｚ値の補正を行なう場合 但し、第４図ｉ）に示す点ＰＡからＰＢまでのｚＭ算出
について説明する。

この場合には、両累積加算値レジスタ（１３）（１４）
およびパイプライン・レジスタ（１８）から第４図（Ｆ
）（Ｇ）（）Ｉ）に示すようにそれぞれ前のぬりつぶし
方向の最後の補間値Ｅｚ５．Ｅｚ５５が出力されている
状態において、第４図（Ｂ）に示すようにマルチボート
・レジスタ・ファイル（１１）から先ず稜線方向の勾配
値ｄｚｏ１／ｄｙ０１が出力され、次いでぬりつぶし方
向の勾配値ｄ　ｚ　／　ｄ　ｘが出力され続ける。上記
勾配値ｄｚｏ１／ｄｙｏ１は、同図（Ｃ）に示すように
、そのまま双方向シフト・レジスタ（１２）から出力さ
れ、稜線用累積加算値レジスタ（１３）に保持されてい
る値Ｅｚ５と共に加算器（１７）に供給される（同図（
Ｄ）（Ｅ）参照）。

したがって、加算器（１７）によって加算が行なわれる
ことにより新たな稜線上のｚｆ［Ｅｚ６が得られ、両累
積加算値レジスタ（１３）（１４）に供給されるので、
その後は両累積加算値レジスタ（１３）（１４）から上
記ｚ　ｉｉ　Ｅ　ｚ　６が出力される（同図（Ｆ）（Ｇ
）参照）。

その後は、先ず、マルチボート・レジスタ・ファイル（
１１）からの出力データを受けて双方向シフト・レジス
タ（１２）が勾配値ｄ　ｚ　／　ｄ　ｘを出力し、次い
で、双方向シフト・レジスタ（１２）を順次１ビツトず
つ右シフトさせることにより順次勾配値ｄｚ／２ｄｘ、
　　ｄｚ／４ｄｘ、　　ｄｚ／８ｄｘ。

ｄ　ｚ　／　１６　ｄ　ｘを出力する（同図（Ｃ）参照
）。

そして、ぬりつぶし用累積加算値レジスタに保持されて
いる値Ｅｚ６に対して勾配値ｄ　ｚ　／　２　ｄ　ｘ　
。

ｄ　ｚ　／　４　ｄ　ｘ　、　ｄ　ｚ　／　８　ｄ　ｘ
　、　ｄ　ｚ　／　１６　ｄ　ｘを順次累積加算するこ
とによりＺ値の補正を達成できる。例えば、Ｘ座標値の
小数部が二進数で、１０１０である場合には、値が“１
°の桁に対して対応する勾配値を選択し、値が“０°で
ある場合には、勾配値に代えて“０°データを選択すれ
ばよく（同図（Ｄ）参照）、最終的に補正された２値Ａ
ｚ３を得ることができる。尚、途中の２値は、ＡｚＯ−
Ｅｚ６　＋ｄｚ／２ｄｘ、Ａｚｌ−ＡｚＯ１Ａｚ２　＝
Ａｚｌ　＋ｄｚ／８ｄｘ、Ａｚ３−Ａｚ２である。

その後は、Ａｚ３をぬりつぶし方向の２値の初期値とし
て勾配値ｄ　ｚ　／　ｄ　ｘの累積加算を行なうことに
より、順次２値ｚ　６１．　　ｚ　１３２・・・を得る
ことができる。

尚、第４図（Ａ）は、クロック信号出力を示す。

以下、上記処理を必要回数だけ反復することにより図形
の描画を達成できる。

〈実施例２〉 第５図はこの発明の境界発生装置を組み込んだ図形描画
装置の他の実施例を示すブロック図であり、第１図の実
施例と異なる点は、勾配値レジスタ（２）およびマルチ
プレクサ（７）に代えて勾配値、および定数値“０００
０．ＦＦＦＦ　（ＨＥＸ）“。

“ＦＦＦＦ、ＦＦＦＦ　ＣＨＥＸ）″を保持し、選択的
に読み出し可能なマルチボート・レジスタ・ファイルま
たはマルチボート・メモリ（９）を用いる点のみである
。

したがって、この実施例の場合には、マルチボート・レ
ジスタ・ファイルまたはマルチボート・メモリ（９）か
ら勾配値または定数値を選択して読み出すだけで第１図
の実施例と同様の作用を達成できる。

〈実施例３〉 第６図はこの発明の境界発生装置を組み込んだ図形描画
装置のさらに他の実施例を示すブロック図であり、第２
図に示す構成に加えて、小数部切り上げ用の定数値“０
０００．ＦＦＦＦ　（ＨＥＸ）°を保持する第１定数値
レジスタ（１９）と、小数部を切り上げて１だけ減算す
るための定数値“ＦＦＦＦ、ＦＦＦＦ　（ＨＥＸ）”を
保持する第２定数値レジスタ（２０）とを設け、稜線用
累積加算結果レジスタ（１３）、ぬりつぶし用累積加算
結果レジスタ（１４）の内容、第１定数値レジスタ（１
９）の内容、第２定数値レジスタ（２０）の内容をマル
チプレクサ（Ｉ６）により選択するようにしている。

したがって、この実施例の場合にも、上記実施例と同様
に平面ポリゴンの内部に位置する境界を発生できるとと
もに、ｚ値の補正をも達成できる。

尚、この実施例の場合には、初期値を累積加算値レジス
タに移した後に定数値を加算するのではなく、初期値に
定数値を加算した状態で累積加算値レジスタに供給でき
るので、全体としての図形描画速度を多少向上させるこ
とができる。

尚、この発明は上記の実施例に限定されるものではなく
、例えば、双方向シフト・レジスタ（１２）に代えて一
方向シフト・レジスタを採用することが可能である他、
この発明の要旨を変更しない範囲内において種々の設計
変更を施すことが可能である。

〈発明の効果〉 以上のように第１の発明は、隣合う平面ポリゴンの全て
について該当する平面ポリゴン内部のぬりつぶし画素の
みを発生できるので、境界を共有するという不都合を解
消できるという特有の効果を奏する。

第２の発明は、構成を簡素化でき、しかも第１の発明と
同様の作用を達成できるという特有の効果を奏する。

第３の発明は、ぬりつぶし描画開始側の境界発生を高速
に達成でき、全体としての描画速度を高速化できるとい
う特有の効果を奏する。

【図面の簡単な説明】

第１図はこの発明の境界発生装置を組み込んだ図形描画
装置の一実施例を示すブロック図、第２図は奥行き値の
補間演算を行なう補間演算部の構成を示すブロック図、 第３図および第４図は、それぞれ第２図の補間演算部の
動作を説明するタイミング・チャート、第５図はこの発
明の境界発生装置を組み込んだ図形描画装置の他の実施
例を示すブロック図、第６図はこの発明の境界発生装置
を組み込んだ図形描画装置のさらに他の実施例を示すブ
ロック図、 第７図は従来の図形描画装置の構成を示すブロック図。 （１）・・・累積加算値レジスタ、（２）・・・勾配値
レジスタ、（３）・・・加算器、（４）（１９）・・・
第１定数値レジスタ、（５）（２０）・・・第２定数値
レジスタ、（７）・・・マルチプレクサ、 （１１）・・・マルチボート・レジスタ・ファイル、（
１４）・・・ぬりつぶし用累積加算結果レジスタ、（１
５）・・・マルチプレクサ、（１７）・・・加算器、第
５図

Claims (1)

1. 【特許請求の範囲】 １、平面ポリゴンの稜線補間データまたはぬりつぶし累
   積加算値を保持する累積加算値保持手段（１）と、ぬり
   つぶし方向の勾配値を保持する勾配値保持手段（２）と
   、小数部切り上げ用の定数値を保持する第１定数値保持
   手段（４）と、小数部を切り上げて１だけ減算するため
   の定数値を保持する第２定数値保持手段（５）と、勾配
   値保持手段（２）、第１定数値保持手段（４）および第
   ２定数値保持手段（５）の内容を選択する選択手段（７
   ）と、累積加算値保持手段（１）の内容と選択手段（７
   ）により選択された内容とを加算して再び累積加算値保
   持手段（１）に供給する加算手段（３）とを含むことを
   特徴とする平面ポリゴンの境界点発生装置。 ２、勾配値保持手段（２）、第１定数値保持手段（４）
   および第２定数値保持手段（５）がマルチポート・レジ
   スタ・ファイルまたはマルチポート・メモリである上記
   特許請求の範囲第１項記載の平面ポリゴンの境界発生装
   置。 ３、平面ポリゴンの稜線補間データまたはぬりつぶし累
   積加算値を保持する累積加算値保持手段（１４）と、ぬ
   りつぶし方向の勾配値を保持する勾配値保持手段（１１
   ）と、小数部切り上げ用の定数値を保持する第１定数値
   保持手段（１９）と、小数部を切り上げて１だけ減算す
   るための定数値を保持する第２定数値保持手段（２０）
   と、累積加算値保持手段（１４）、第１定数値保持手段
   （１９）および第２定数値保持手段（２０）の内容を選
   択する選択手段（１６）と、勾配値保持手段（１１）の
   内容と選択手段（１６）により選択された内容とを加算
   して再び累積加算値保持手段（１４）に供給する加算手
   段（１７）とを含むことを特徴とする平面ポリゴンの境
   界点発生装置。