JPS6367686A - 並列画像生成処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概要］ 本発明は、視点から発した探査用光線に）Ｊづいて３次
元空間上の物体を探知し、当該物体の像を２次元平面上
に（与る画像生成処理装置において、複数のプロセッサ
がそれぞれ複数の小矩形領域を担当し、且つ近接プロセ
ッサ間での情報交換により担当プロセッサを動的にｍ　
ＩＲＬで割り当て負荷分散を可能にし、しかも各プロセ
ッサーは担当づる？！２数の小矩形内の画（象の類似性
を利用するようにして、高速の画像生成処理を行うよう
にしたものである。

［産業上の利用分野］ 本発明は、画像生成処理！Ａ置特に光線追跡法或いはそ
れに類似する方法を利用して画像生成を行うに当たって
、複数のプロセッサにおいて処理負荷を動的に切り替え
て負荷を平均化することを可能にした並列画像生成処理
装置に関する。

［従来の技術］ 従来から３次元空間上の物体の像を２次元平面上に得る
画像生成処理装置にＪ３いては、一般に光線追跡法と呼
ばれる方法を利用することが行われている。第６図はこ
の方式を説明するための説明図である。図中、１は視点
、２は光源、３は探査用光線、４は物体、５は２次元平
面スクリーン、６は反射点、７はスクリーン上の画素、
ｉ−１゜ｉ、ｉ＋１はそれぞれのスクリーン上の短形の
領域を表わしている。

光源２から発せられた光が物体４に当たって反Ｏｊされ
視点１に至るが、この光の通路上に設けたスクリーン５
に当該光の輝度に対応する明るさを持つ点を描くことに
よって物体４の像をスクリーン上に描こうとするもので
ある。上記光線追跡法の場合、不必要な処理を削減する
ために、上述とは逆に視点１から探査用光線を疑似的に
発する形をとり、当該光線３が物体４によって反射され
て光源２に達したとき当該探査用光線３がスクリーン５
と交差するドツト位置に像を描くようにする。

このような処理をシミュレーションする場合、スクリー
ン上の画素毎に独立に処理を行うことができることから
スクリーンをｎ個の矩形領域に分け、ｎ台のプロセッサ
に割り振って並列処理によって高速処理が可能である。

第８図はそのような処理を行うための装置の構成図で、
スクリーン上の各矩形領域の画像を担当するｎ台のプロ
セッサ（Ｐ　Ｕ　ｏ　＝　Ｐ　ＬＪ　Ｔ＋−１＞がバス
９を介してホストコンピュータ８に接続され、ホストコ
ンピュータの管理の下にそれぞれ独立に動作するように
なっている。

［発明が解決しようとする問題点］ 従来の方式では、通常一部のプロセッサ（例えばスクリ
ーン中央部を担当するプロセッサ）に処理負荷が集中す
ることとなり、均一な並列処理とはならない。

そのため例えば、１台のプロセッサが担当するスクリー
ン上の領域を矩形ではなく飛び飛びの画素とすることに
より、負荷の確率的な平均化を行う手法がある。光線追
跡法を画素単位に独立に行う限りは、この方法によって
も十分な負荷分散の効果が得られる。しかしながら、一
般に小矩形領域を処理単位としてこの領域内の画素の輝
度が類似しているときは、すべての画素にわたって光線
ｊＤ跡は行わず、補間によって中間の画素の輝度を求め
ることにより大幅に処理属を削減できるが、上記飛び飛
びの画素担当方式では、補間による高速化手法が適用で
きないという欠点がある。

又、別の方式としては、スクリーンをプロセッサの数よ
り多い個数の小矩形領域に分割し、最初は各プロセッサ
に小矩形領域を一つずつ割り撮っておき、処理を終了し
たプロセッサに対しては未処理の小矩形領域を順次ｖｊ
り当てることにより動的に負荷の分散を図るものがある
。しかし、この方式では多数プロセッサを一本のバス経
由でホストコンピュータと通信する必要があり、このこ
とが処理のオーバーヘッドを生むという欠点となる。

本発明はこのような点に鑑みてなされもので、動的な負
荷分散を可能にし且つ各プロセッサが（■当する複数の
小矩形内の画像の類似性を利用して補間処理を行うこと
により高速に画像生成処理を行うことのできる並列画像
生成方式を提供することにある。

［問題点を解決するための手段］ 第１図は本発明の原理ブロック図である。図において、
１１はそれぞれが独立にスクリーンの一部の画素におけ
る像を求めることができる縦横それぞれｎｌのプロセッ
サ、１２はこれら複数個のプロセッサを２次元状の配列
でかつ互いにエンドレス接続となるように接続する通信
路である。このようにｎｘｎのマトリクス状に配された
プロセッサ１１はセルとも称されエンドレス接続の通信
路と相まって所謂ドーナツ状ネットワークを構成する。

［作用］ 本発明はプロセッサ１１とホス１−コンピュータ〈図示
せず、〉が通信することなく、２次元格子状に接続され
たプロセッサを近隣のプロセッサ間とのみ通信可能とす
ることにより負荷の動的な分散を行う。この場合、プロ
セッサ間の通信路の帯域が全体としてホスト・コンピュ
ータ間のバスの帯域に比較して十分に広いため、負荷の
分散のための通信はオーバーヘッドが少ない。又、処理
単位を小矩形としているため補間による高速化手法を同
時に適用することができる。

本発明では、視点から発した探査用光線が３次元空間上
の物体によって反射や透過を受けて光源に到達するか否
かを探知して前記物体の像を２次元平面上に得る画像生
成装置において、複数のプロセッサ１１に前記２次元平
面上の複数の小矩形領域を担当させ、画像生成を行う際
に上下左右の近隣のプロセッサの内から負荷の少ないプ
ロセッサを選出して担当を割り当てるようにすることに
より、動的に負荷分散を行い、且つ各プロセッサが担当
する複数の小矩形内の画像の類似性を利用して中間の画
素に対して補間処理により画作を１４７るようにするこ
とにより高速な画像生成処理を可能にする。

［実施例コ 以下、図面を参照して本発明の実施例を詳細に説明する
。第２図は本発明の一実施例を示す構成ブロック図であ
る。第１図と同一のものは同一の符号を付して示す。図
において、１１はセルと称するプロセッサエレメント、
１３はホストコンピュータ、１４はセルとポストコンピ
ュータを結ぶデータ放送バス、１５は画像が表示される
カラーモニタ、１６はセル内に生成された画像データを
カラーモニタ１５に送るために使用される両独表示バス
である。各セルのプロセッサは上下左右に隣接するプロ
セッサと前記したエンドレス通信路１４で結ばれている
。末端のセルはそれぞれ反対側のセルのプロセッサと接
続され、全体としてエンドレスの連結構造となっている
。本発明はこのように２次元格子状に接続されたプロセ
ッサアレイ上で実現される。

さて、プロセッサの個数を第２図に示すように縦横それ
ぞれｎ個（従って、ｎｘｎ個のプロセッサが必要）とし
、又、スクリーンを第３図に示すように縦横それぞれｎ
×ｋ個に分割する（従って、スクリーンは（ｎ×ｋ）２
の矩形に分割される）。分割された最小の矩形を小矩形
Ｒと呼ぶことにする。

そして、プロセッサＰ　（ｉ　、　ｊ　）　　（ｔ　、
　ｊ　＝０゜１、・・・・・・、ｎ−１）の担当領域と
して、Ｒ（ｎｘ　Ｌ＋ｉ　、　ｎｘ　Ｌ＋ｊ　）　　　
　＝・（１）但し、Ｌ＝０．１．・・・・・・、に−１
で表される小矩形Ｒを左上とし、それから右及び下の方
向にそれぞれ８個（Ｓ≦ｎ）にわたる矩形群の領域と定
める。この領域は８２個の小矩形からなる矩形領域であ
り、これをブロックと呼ぶ。

ブロックの一例を第４図に示す。例えば、プロセッサＰ
（０，０＞の担当する領域（（１）式から明らかなよう
に全部でに２個ある）の一つは、第３図に示すように、
左上ｒ（（０，０＞の小矩形と右下Ｒ（Ｓ−１，８−１
）の小矩形を対角とする矩形領域である（この場合の矩
形のアドレスは第４図に示す矩形アドレスと同じになる
）。

更にわかりやスフ説明すれば、今仮にｎ　＝ｋ　＝３．
８−２とすると、プロセッサは９周であり、スクリーン
が９×９個の小矩形に分割され、各ブロックは４個の小
矩形で構成されることになる。

例えば、プロセッサＰ　（０，０）は第５図（イ）に示
すような領域の９個のブロックを（■当し、Ｐ（１，１
＞は第５図（ロ）に示すような領域の９個のブロックを
担当することになる。

このような割り撮りを行うと、スクリーンの全ての小矩
形のそれぞれについて８２台のプロセッサが担当しくｑ
ることになる。実際には何れか一つのプロセッサがその
小矩形を担当づ−ることになるが、とのプロセッサに担
当させるかを動的に決めることにより、負荷の分散が可
能となる。

次に隣接プロセッサ間の通信を用いた負荷分散処理法に
ついて説明する。プロセッサＰ（ｉ、ｊ）が担当するあ
る任２依の１ブロツク（８２個の小矩形からなる）を考
える。そのブロック内の小矩形領域Ｒ１ｘ、ｙ）（ｘ、
ｙ＝ｏ＋　１．・・・・・・、５−１）の担当するプロ
セッサは、 Ｐ　（（ｉ　−８＋　１＋ｘ　）％ｎ　、　　（ｊ−８
＋１＋ｙ）％ｎ） Ｐｌｉ＋Ｘ）％ｎ、（ｊ＋ｙ）％ｎ）の２つを対角に持
つ矩形状の８２個のプロセッサである。

ここに、記号％は、剰余の計算を行うための演算子で、
左項を６項で割ったときの余りの数値を演篩結果とする
ものである。

例えば、Ｓ＝２とした場合、ブロック内の小矩形領域Ｒ
（０，Ｏ）を担当する各プロセッサは、第６図のように
なる（担当領域の重畳関係を明瞭にするために各プロセ
ッサの担当領域を少しずらせて描いである）。

動的負荷分散の手順は次のように行う。各プロセッサは
担当する小短形領域内の未処理のものを選んで処理する
。各プロセッサは新しい小矩形領域の処理を開始したら
、この小矩形ｆｔ域を共通に担当する５２−１個の近隣
のプロセッサに小矩形領域のアドレスと自分のプロセッ
サ番号を通知する。通知を受けたプロセッサはこの領域
に処理済のマークを付けておく。もし、通知が発せられ
てから届くまでの間に他のプロセッサが同じ小矩形領域
の処理を開始したときは、予め設定しであるプロセッサ
間の優先順位に基づき、優先度の低い方がこの小矩形の
処理をキャンセルする。このような手続はホストコンピ
ュータ１３を経由することなく、近接プロセッサ間で行
われる。処理の結果はカラーモニタ１５に表示される。

このようにして各プロセッサの負荷を動的に分散させて
均等化することができる。尚、処理単位を小矩形とした
ことにより、類似性のある画像が並ぶような場合にはそ
の中間に在る小矩形における画像を補ｌｆｆ１９１Ｂ理
により求めることができるので、そのような処理手法を
採用することにより画像生成の高速化を図ることができ
る。

［発明の効果］ 以上詳細に説明したように本発明によれば、ホストコン
ピュータとプロセッサ群とが通信を行うことなしに、プ
ロセッサが近接プロセッサとのみ通信を行って動的な負
荷分散を行うことができ、負荷分散のためのオーバーヘ
ッドを１１減することができる効果がある。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、第２図は本発明の一
実施例を示す構成ブロック図、第３図はスクリーンの分
割小矩形領域を示す図、第４図はブロック内の小矩形の
アドレスを示す図、第５図はプロセッサの担当領域を説
明するための説明図、第６図は小矩形を共通に担当する
プロセッサの一群を示すための説明図、第７図は光線追
跡法を説明するための説明図、第８図は従来の装置の構
成図である。 図において、 １１はプロセッサ、 １２はホストコンピュータ、 １３はデータ放送バス、 １４は通信路、 １５は画像表示バス、 １６はカラーモニタである。 特許出願人　富　　士　　通　　株　　式　　会、７社
−］−、本発明の原理ブロック図 第１図 スクリーン平面の分割小矢凹分１に 第３図 ブロック内の小矩形の７ドレス 第４図

Claims (1)

1. 【特許請求の範囲】 視点から発した探査用光線が３次元空間上の物体によつ
   て反射乃至は透過を受けて光源に到達するか否かを探知
   し、前記物体の像を２次元スクリーン平面上に得る画像
   生成処理装置において、それぞれが独立に前記スクリー
   ンの一部の画素における像を求めることができる縦横そ
   れぞれｎ個のプロセッサ（１１）と、 この複数のプロセッサを２次元状の配列でかつ互いにエ
   ンドレス接続となるように接続する通信路（１２）とを
   具備し、 前記スクリーンを縦横それぞれｎ×ｋ個の小矩形Ｒに分
   割し、プロセッサＰ（ｉ、ｊ）（但し、ｉ、ｊ＝０、１
   、・・・・・・、ｎ−１）の担当領域として、小矩形Ｒ
   （ｎ×Ｌ＋ｉ、ｎ×Ｌ＋ｊ）（但し、Ｌ＝０、１、・・
   ・・・・、ｋ−１）を左上として、それから右及び下の
   方向にＳ個（Ｓ≦ｎ）分の長さを有する矩形状の領域と
   定め、 これらの各矩形状の領域（ブロック）内の各小矩形領域
   Ｒに対して担当し得る近隣のプロセッサの内で予め定め
   た優先順位の高いプロセッサが優先して処理に当たるよ
   うに割り振って負荷分散を均等化したことを特徴とする
   画像生成処理装置。